百度之星2017资格赛1003[度度熊与邪恶大魔王]

1003题目[度度熊与邪恶大魔王]

题目描述

给定n个怪兽的血量和防御值，以及m个技能的伤害和花费。求打败n个怪兽需要的花费最小值

题目思路

完全背包 从题目中所说，每个技能可以使用无限次得知可以通过完全背包来解决。

复杂度估计 如果对n个怪兽，每个计算m个技能消灭怪兽的最小花费计算，那么需要 a*b*m*a = 1000 * 10 * 1000 * 1000（即n个怪兽的血量和防御共有1000*10种，每次计算最小花费需要完全背包的时间复杂度1000*1000）这种做法必然超时

考虑防御的范围为10 因此，考虑对于每一个怪兽的血量虽然可能不同，但是相同防御的情况下，对于f[v]来说解都是一样的。所以只需要考虑当前防御值是否计算过，如果计算过，那么直接可以在f[v]中得到答案 复杂度 b*m*a = 10 * 1000 * 1000

代码

在没有完全理解解法前，建议不要先看代码

#include<iostream> #include<stdio.h> #include<memory.h> using namespace std; int main(){ int a[100010], b[100010]; int k[1010],p[1010]; int vdp[2010][11]; bool flag; int N, M; __int64 ans; //long long ans; int INF = 100000000; while(scanf("%d%d", &N,&M)!=EOF){ ans = 0; for(int i=0;i<N;i++){ scanf("%d%d",&a[i],&b[i]); } for(int i=0;i<M;i++){ scanf("%d%d",&k[i],&p[i]); } for(int i=0;i<11;i++){ for(int k=1;k<=2000;k++){ vdp[k][i] = INF; } vdp[0][i] = 0; } for(int i=0;i<11;i++){ for(int j=0;j<M;j++){ if(p[j]-i>0){ for(int v=p[j]-i; v<=2000;v++){ vdp[v][i] = min(vdp[v][i], vdp[v-(p[j] - i)][i]+k[j]); } } } } for(int i=0;i<N;i++){ flag = false; int max = INF; for(int v=a[i];v<=a[i]+1000;v++){ //cout<<v<<" "<<vdp[v]<<endl; if(vdp[v][b[i]]!=INF){ if(max>vdp[v][b[i]]){ max = vdp[v][b[i]]; } } } if(max != INF){ ans += max; flag = true; } if(!flag) break; } if(!flag) printf("-1\n"); //cout<<-1<<endl; else{ printf("%I64d\n",ans); //cout<<ans<<endl; } } }