度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。
邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。
度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。
当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。
如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。
Input本题包含若干组测试数据。
第一行两个整数n，m,表示有n个怪兽，m种技能。
接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。
再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<=n<=100000
1<=m<=1000
1<=a[i]<=1000
0<=b[i]<=10
0<=k[i]<=100000
0<=p[i]<=1000
Output对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1
Sample Input 1 2 3 5 7 10 6 8 1 2 3 5 10 7 8 6 Sample Output 6 18 思路：完全背包问题 代码如下： [cpp] view plain copy print ? #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=2000+5; const int N1=1000000+5; typedef long long ll; ll n,m; ll a[N1],b[N1],k[N],p[N];//注意数组范围扩大一点，题目上要求10万，但是如果是定义大小为10万的话会wa ll dp[N][15]; int main() { while(cin>>n>>m) { ll hpx=0,upx1=0,upx2=0; //upx1:最大防御力，hpx最大生命值，upx2最大攻击力 for(int i=0;i<n;i++) { cin>>a[i]; hpx=max(hpx,a[i]); cin>>b[i]; upx1=max(upx1,b[i]); } for(int i=0;i<m;i++) { cin>>k[i]; cin>>p[i]; upx2=max(upx2,p[i]); } if(upx2<=upx1)//如果最大攻击力小于最大防御力，说明无法消灭 { printf("-1\n"); continue; } memset(dp,0,sizeof(dp)); //i：防御，j：怪物生命值 //dp[j][i] 表示打到生命值为j 防御力为i的怪物需要消耗的晶石 for(int i=0;i<=10;i++)//因为防御力是从1~10的，所以从防御开始 打表 { for(int j=1;j<=hpx;j++) { //默认赋予一个很大的值 ，最为晶石消耗量 dp[j][i]=0x3f3f3f3f; for(int u=0;u<m;u++)//对于每种血量和防御力的怪物，遍历每种攻击方式 { ll sh=p[u]-i;//计算出当前伤害值 if(sh<=0) continue; else if(sh>=j) //伤害值大于当前生命值 dp[j][i]=min(dp[j][i],k[u]); //需要消耗的晶石== min(其他攻击方式消灭怪物所需的最小晶石,当前消耗的晶石) else//伤害值小于生命值但大于0 dp[j][i]=min(dp[j][i],dp[j-sh][i]+k[u]); //需要消耗的晶石==min(其他攻击方式消灭怪物所需的最小晶石,当前消耗的晶石量+消灭怪物(生命值=需要达到的伤害-当前造成的伤害，防御值相同)所消耗的晶石的最优解) } } } ll ans=0; for(int i=0;i<n;i++) ans+=dp[a[i]][b[i]];//最后把每种最解相加，得出最小消耗量 cout<<ans<<endl; } return 0; }