本题我们可以类比背包
背包dp[i][j] 表示再有i个物品下j个空间所获得的最大价值
本题dp[i][j] 可以表示干掉i个血量j个防御力下的最小花费
我们看其实我们就是在不同血量之间转移
如果当前技能的攻击力 > 当前防御力
如果攻击力能干掉怪物那么dp[i][j] = min(花费,dp[i][j]);
如果干不掉 dp[i][j] = min(dp[i-伤害] [ j]+花费 , dp[i][j]);也就是在干掉i-伤害值下的花费 再加使用这次技能的花费
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100010; const int inf = 0x3f3f3f3f; ll n,m,k[1010],p[1010],a[maxn],b[maxn]; ll dp[1010][15]; int main() { while(~scanf("%d%d",&n,&m)) { ll ml=0,mf=0; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; ml = max(ml,a[i]); mf = max(mf,b[i]); } ll ma=0; for(int i=1;i<=m;i++) { cin>>k[i]>>p[i]; ma = max(p[i],ma); } memset(dp,0,sizeof(dp)); if(ma<=mf){ puts("-1"); continue; } for(int j=1;j<=ml;j++) { for(int i=0;i<=10;i++) { dp[j][i] = inf; for(int u=1;u<=m;u++) { ll h = p[u]-i; //cout<<j-h<<endl; //system("pause"); if(h<=0)continue;//伤害值小于防御值 if(h>=j)//可以干掉 dp[j][i] = min(dp[j][i],k[u]); else dp[j][i] = min(dp[j][i],dp[j-h][i]+k[u]); } } } ll ans=0; for(int i=1;i<=n;i++) { ans+=dp[a[i]][b[i]]; } printf("%lld\n",ans); } return 0; }
