P1802 5 倍经验日 题解

· · 题解

P1802 5 倍经验日 题解

一道\blue{dp题},见代码

#include <iostream>
using namespace std;
const int N = 1110;
int dp[N];
int n,x;
int win[N],lose[N],use[N];
int main(){
    cin >> n >> x;
    for(int i = 1;i <= n;i++) 
        cin >> lose[i] >> win[i] >> use[i];
    for(int i = 1;i <= n;i++){
        for(int j = x;j >= use[i];j--)
            dp[j] = max(dp[j]+lose[i],dp[j-use[i]]+win[i]);
        for(int j = use[i]-1;j >= 0;j--)
            dp[j] += lose[i];
    }
    printf("%lld",5ll*dp[x]);//强制类型转换同时*5
    return 0;
}
/*
    状态:dp[j]表示前j次获得的经验值的最大值
    转移:dp[j] = max(dp[j]+lose[i],dp[j-use[i]]+win[i])*5;
    答案:dp[x] 
*/