动态规划五倍经验C++

洛谷原题：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
#include
#include
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[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;
}

下面这个是我的：

#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开始。因为就算没有药也有失败经验*_*.(要注意细节啊，满意就给个采纳吧^_^)

该回答引用ChatGPT

你的转移方程是正确的，但可能存在一些细节问题，导致得分不够理想。以下是一些可能需要注意的地方：

数组越界：在数组中，下标从0开始。在你的代码中，你使用了从1开始的下标，因此需要将数组大小增加1，如下所示：

int n,x,lose[1003],win[1003],use[1003];
long long f[1003][1003];

数据类型不匹配：题目中给出的exp是一个整数，但你使用了long long来存储结果。这并不会导致错误，但可能会浪费内存。你可以使用一个普通的整数变量来存储结果。

边界条件：在循环中，你将f[0][j]设置为0。但在第0个人之前，没有其他人，因此它不应该产生任何经验值。你应该将f[0][j]初始化为负无穷，表示在前0个人时，使用j个药品无法获得经验值。

求解结果：在你的代码中，你没有输出结果。你需要将dp函数的结果打印出来。

根据以上建议，你可以尝试以下代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n, x;
int lose[1003], win[1003], use[1003];
int f[1003][1003];

int dp(int n, int x) {
    //初始化边界条件
    for(int j=0; j<=x; j++) f[0][j] = -1;

    for(int i=1; i<=n; i++) {
        for(int j=0; j<=x; j++) {
            f[i][j] = f[i-1][j] + lose[i]; //如果不用药品，直接输
            if(j >= use[i]) { // 如果有药品可以用
                f[i][j] = max(f[i][j], 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];
    int exp = dp(n,x);
    cout << 5 * exp << endl;
    return 0;
}