动态规划五倍经验C++

Question

洛谷原题：https://www.luogu.com.cn/problem/P1802
初学DP，只拿了40分，但总感觉代码没问题
转移方程：f[i][j]=max(f[i-1][j]+lose[i],f[i-1][j-use[i]]+win[i])

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,lose[1002],win[1002],use[1002];
long long f[1002][1002];
//f[i][j]表示用j瓶药拿到前i人的exp
//f[i][j]=max(f[i-1][j]+lose[i],f[i-1][j-use[i]]+win[i]) 
long long dp(int n,int x){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=x;j++){
            if(j<use[i])f[i][j]=f[i-1][j]+lose[i];
            else f[i][j]=max(f[i-1][j]+lose[i],f[i-1][j-use[i]]+win[i]);
        }
    }
    return f[n][x];
}

int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>lose[i]>>win[i]>>use[i];
    long long exp=dp(n,x);
    cout<<5*exp;
    return 0;
}

Answer 1

下面这个是我的：

#include<bits/stdc++.h>
using namespace std;
int n,x,l[1005],w[1005],u[1005],dp[1005];
int main(){
    scanf("%d %d",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&l[i],&w[i],&u[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=x;j>=u[i];j--){
            dp[j]=max(dp[j]+l[i],dp[j-u[i]]+w[i]);
        }
        for(int j=u[i]-1;j>=0;j--){
            dp[j]+=l[i];
        }
    }
    printf("%lld\n",5*dp[x]);
}

你的其实没啥问题，只不过你的dp药要从0开始。因为就算没有药也有失败经验*_*.(要注意细节啊，满意就给个采纳吧^_^)