度度熊与邪恶大魔王
邪恶大魔王的麾下有n个怪兽&＃xff0c;每个怪兽有a[i]的生命值&＃xff0c;以及b[i]的防御力。
度度熊一共拥有m种攻击方式&＃xff0c;第i种攻击方式&＃xff0c;需要消耗k[i]的晶石&＃xff0c;造成p[i]点伤害。
当然&＃xff0c;如果度度熊使用第i个技能打在第j个怪兽上面的话&＃xff0c;会使得第j个怪兽的生命值减少p[i]-b[j]&＃xff0c;当然如果伤害小于防御&＃xff0c;那么攻击就不会奏效。
如果怪兽的生命值降为0或以下&＃xff0c;那么怪兽就会被消灭。
当然每个技能都可以使用无限次。
请问度度熊最少携带多少晶石&＃xff0c;就可以消灭所有的怪兽。
Input本题包含若干组测试数据。
第一行两个整数n&＃xff0c;m,表示有n个怪兽&＃xff0c;m种技能。
接下来n行&＃xff0c;每行两个整数&＃xff0c;a[i],b[i]&＃xff0c;分别表示怪兽的生命值和防御力。
再接下来m行&＃xff0c;每行两个整数k[i]和p[i]&＃xff0c;分别表示技能的消耗晶石数目和技能的伤害值。
数据范围:
1<&＃61;n<&＃61;100000
1<&＃61;m<&＃61;1000
1<&＃61;a[i]<&＃61;1000
0<&＃61;b[i]<&＃61;10
0<&＃61;k[i]<&＃61;100000
0<&＃61;p[i]<&＃61;1000
Output对于每组测试数据&＃xff0c;输出最小的晶石消耗数量&＃xff0c;如果不能击败所有的怪兽&＃xff0c;输出-1
Sample Input
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6
Sample Output
6
18
思路详见代码。
#include
#include
#include<string.h>
#include
#define MAX 1005
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;int dp[15][2005];
int a[100005],b[100005];
int k[1005],p[1005];
int max(int x,int y){return x>y?x:y;
}
int min(int x,int y){return x
}
int main()
{int n,m,i,j,l;while(~scanf("%d%d",&n,&m)){memset(dp,INF,sizeof(dp));int maxa&＃61;0,maxb&＃61;0;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d%d",&a[i],&b[i]);maxa&＃61;max(maxa,a[i]);maxb&＃61;max(maxb,b[i]);}for(i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d",&k[i],&p[i]);}for(i&＃61;0;i<&＃61;maxb;i&＃43;&＃43;){dp[i][0]&＃61;0;for(j&＃61;1;j<&＃61;m;j&＃43;&＃43;){if(p[j]>i){for(l&＃61;0;l<&＃61;maxa;l&＃43;&＃43;){if(p[j]-i>l) dp[i][l]&＃61;min(dp[i][l],k[j]);else dp[i][l]&＃61;min(dp[i][l],dp[i][l-(p[j]-i)]&＃43;k[j]);}}}}ll ans&＃61;0;int f&＃61;0;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(dp[b[i]][a[i]]&＃61;&＃61;INF){f&＃61;1;break;}ans&＃43;&＃61;dp[b[i]][a[i]];}if(f&＃61;&＃61;1) printf("-1\n");else printf("%I64d\n",ans);}return 0;
}
京公网安备 11010802041100号