首先思考一下能否用贪心求解
1.每次选消耗最少的:题中所给样例即可否决此解法;
2.每次在允许范围内选经验最多的:样例能通过,但如果把第二组消耗改为7,其余均改为1即无法正确求解。
这就基本否决了贪心法,考虑按以下步骤用动态规划求解。
Step1.数组下标与值的含义
dp[i][j]代表前i个人,当前药量为j的最大经验。
Step2.初值条件
dp[0][0]=0。
Step3.递推关系
如果只能输(j<use[i]),则dp[i][j]=dp[i-1][j]+lose[i]
如果能赢,则分不用药与用药两种情况。 dp[i][j]=max(dp[i-1][j],dp[i-1][j-use[i]]+win[i])
Step4.写出代码
#include <cstdio>
#include <algorithm>
#define long long long
const int MAX_MAN=1001,MAX_MED=1001;
using namespace std;
long dp[MAX_MAN][MAX_MED];
int win[MAX_MAN],lose[MAX_MAN],use[MAX_MAN];
int main(){
int n,x;
long res=0;
scanf("%d%d",&n,&x);
for(int i=1; i<=n; i++) {
scanf("%d%d%d",&lose[i],&win[i],&use[i]);
dp[i][0]=dp[i-1][0]+lose[i];
}
res=dp[n][0];
for(int i=1; i<=n; i++) {
for(int j=1; j<=x; j++) {
if(j<use[i]) { //必输,不用药
dp[i][j]=dp[i-1][j]+lose[i];
}
else {
dp[i][j]=max(dp[i-1][j],dp[i-1][j-use[i]]+win[i]);
}
res=max(res,dp[i][j]);
}
}
printf("%lld",res*5);
return 0;
}
发现代码无法通过样例。
原因:不用药也有经验(lose[i])
Step5.完善代码:
将上述代码中的dp[i][j]=max(dp[i-1][j],dp[i-1][j-use[i]]+win[i]);
改为dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
提交记录:
错误原因:默认药量为0时一定不能赢,没有考虑use[i]==0的特殊情况。
修改:将j=1改为j=0,删除dp[i][0]=dp[i-1][0]+lose[i];
一行。能AC。
Step6.优化
注意dp[i]的每一个元素都是通过dp[i-1]转移,因此可参考01背包的思路,省略第一维。为了保证每次都是用的上一个,内层循环应倒序遍历,即:
for(int j=x; j>=use[i]; j--)
dp[j]=max(dp[j],dp[j-use[i]]+win[i]);
for(int j=use[i]-1; j>=0; j--)
dp[j]+=lose[i];
总结:遇到最优解问题时,应当首先考虑贪心,如果贪心无法求解,应考虑动态规划,按照上面的Steps求解。
如果一时无法写出状态转移方程,可以先尝试记忆化搜索。
如果时间充足,为了验证正确性,可以写暴力搜索作为对比,实在不行就把暴力搜索的交上去。