建设企业网站e路护航官网下载,北京5人死亡,如何创建网站详细步骤,网页版梦幻西游东海渔歌怎么玩链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6082 Problem Description
度度熊为了拯救可爱的公主#xff0c;于是与邪恶大魔王战斗起来。邪恶大魔王的麾下有n个怪兽#xff0c;每个怪兽有a[i]的生命值#xff0c;以及b[i]的防御力。度度熊一共拥有m种攻击方… 链接http://acm.hdu.edu.cn/showproblem.php?pid6082 Problem Description
度度熊为了拯救可爱的公主于是与邪恶大魔王战斗起来。邪恶大魔王的麾下有n个怪兽每个怪兽有a[i]的生命值以及b[i]的防御力。度度熊一共拥有m种攻击方式第i种攻击方式需要消耗k[i]的晶石造成p[i]点伤害。当然如果度度熊使用第i个技能打在第j个怪兽上面的话会使得第j个怪兽的生命值减少p[i]-b[j]当然如果伤害小于防御那么攻击就不会奏效。如果怪兽的生命值降为0或以下那么怪兽就会被消灭。当然每个技能都可以使用无限次。请问度度熊最少携带多少晶石就可以消灭所有的怪兽。Input
本题包含若干组测试数据。第一行两个整数nm,表示有n个怪兽m种技能。接下来n行每行两个整数a[i],b[i]分别表示怪兽的生命值和防御力。再接下来m行每行两个整数k[i]和p[i]分别表示技能的消耗晶石数目和技能的伤害值。数据范围:1n1000001m10001a[i]10000b[i]100k[i]1000000p[i]1000Output
对于每组测试数据输出最小的晶石消耗数量如果不能击败所有的怪兽输出-1Sample Input
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6Sample Output
6
18Source
2017百度之星程序设计大赛 - 资格赛 题干 #includecstdio
#includecstring
#includealgorithm
#define LL long long
using namespace std;
const LL INF1e187;
LL n,m,f[155][5507];
LL maxp,max1,max2,ans,mn;
LL a[100007],b[100007],v[100007],p[100007];
void first(){for(int i0;imax2;i)for(int j1;jmax1maxp;j)f[i][j]INF;for(int k0;kmax2;k)for(int i1;im;i){LL nowp[i]-(LL)k;if(now0) continue;for(int j1;jmaxpmax1;j){if(j-now0) f[k][j]min(f[k][j],f[k][j-now]v[i]);else f[k][j]min(f[k][j],v[i]);}}
}
int main()
{while(scanf(%lld %lld,n,m)!EOF){maxpmax1max2ansmn0;for(int i1;in;i){scanf(%lld%lld,a[i],b[i]),max1max(a[i],max1),max2max(max2,b[i]);}for(int i1;im;i){scanf(%lld%lld,v[i],p[i]);maxpmax(maxp,p[i]);}if(max2maxp){printf(-1\n);continue;}first();for(int i1;in;i) ansf[b[i]][a[i]];printf(%lld\n,ans);}return 0;
} 代码 数据怎么大有像背包有递推性质那就dp吧。 f[i][j]表示要杀掉防御为i生命为j的怪兽需要的水晶。 dp时要注意如果不能破防就不要用该技能啦。转载于:https://www.cnblogs.com/CLGYPYJ/p/7390466.html
