这道题的题目描述得好像很烦，大概是要让物理攻击先攻击，然后去攻击魔法攻击，问如何物理攻击可以花最少的魔法攻击花费，当然我们不用输出如何物理攻击，只需要输出最少的魔法攻击花费就可以了，于是我们先预处理dp[i][j]数组表示当一个怪还剩i点生命，j点防御力的时候，最少需要多少魔法石，那么我们预处理出这个之后，显然就可以根据物理攻击进行背包，显然我们有一个体力上限，收益是花费的魔法石个数，花费是对应的需要消耗的体力。然后求最大的省下来的魔法石数就可以了，然后用所有的魔法石数量减去剩下的就是至少要花的啦。
代码：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; long long a[10000],b[10000],k[3200],p[3200],dp[3200][22],f[3200],t[3200]; int n,m,w; int main(){ while(~scanf("%d%d%d",&n,&m,&w)){//n个敌人，m种魔法，w的体力 register long long maxp=0,maxb=0; for(register int i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&t[i]),maxb=max(maxb,b[i]); //a为生命值，b为防御值，t为体力值,k为消耗魔法石数量，p为造成的伤害大小 for(register int i=1;i<=m;i++)scanf("%d%d",&k[i],&p[i]),maxp=max(maxp,p[i]); if(maxb>maxp){puts("-1");continue;}; memset(dp,0x3f3f3f3f,sizeof(dp)); for(register int j=0;j<=12;j++)dp[0][j]=0;//其中dp[i][j]中i表示剩余的生命值,j表示防御力的兵最少需要多少魔法石 for(register int x=1;x<=m;x++){//第一层循环是for魔法 for(register int j=0;j<=10;j++){//第二层for防御力 for(register int i=0;i<=1000;i++){//第三层for生命值 if(p[x]<=j) continue;//造不成伤害 if(i<=p[x]-j) dp[i][j]=min(dp[i][j],k[x]);//消耗的魔法石数量 else if(dp[i][j]>dp[i-(p[x]-j)][j]+k[x]) dp[i][j]=dp[i-(p[x]-j)][j]+k[x]; } } } register long long sum=0; for(register int i=1;i<=n;i++)sum+=dp[a[i]][b[i]]; for(register int i=1;i<=n;i++) for(register int j=w;j>=t[i];j--) f[j]=max(f[j],f[j-t[i]]+dp[a[i]][b[i]]); sum-=f[w]; cout<<sum<<endl; } return 0; }