其他题目就不发博客了（有些也没做出来！！），感觉这次百度之星资格赛题目数据有毒，吐槽，其他题目也不好说，感觉这个题目正常点。 这个题目我当时想到的就是动态规划，但是评论中很多人说是贪心，我一直不理解，认为他们对于贪心和动态规划之间的范畴没有搞清楚（可能是我没搞清楚！有错误请dalao指正），可能有dalao能贪心出来（一脸敬佩）；虽然知道是动态规划问题，可转移方程怎么搞？我一直在想（比较弱！！），想了许多的动态规划的方法，还是用打表的方式（就是每种可能出现的怪兽，根据这组数据的技能和伤害值，用数组记录它消耗的最小晶石数目），这样全部出来了就方便了，将出现的怪兽消耗的最小晶石数目加起来即可；比赛开始一个小时才AC这个题目，一发AC(比较开心)，有dalao有更好的方法请赐教（万分感谢！！）。
AC代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const long long INF=1e15; const int maxn=100000+10; const int maxm=1000+10; struct P{ int live;//怪兽的生命值 int figth;//怪兽的防御力 }p[maxn]; struct V{ int money;//技能的消耗晶石数目 int shai;//技能的伤害值 }v[maxm]; long long ans[maxm][15];//存储每种怪兽需要消耗的最小晶石数目 int n,m; bool cmpp(P a,P b) { return a.figth>b.figth;//以怪兽的防御力从大到小排序 } bool cmpv(V a,V b) { return a.shai>b.shai;//以技能的伤害值从大到小排序 } int main() { while(scanf("%d%d",&n,&m)==2) { int i,j,k; for(i=0;i<n;i++) { scanf("%d%d",&p[i].live,&p[i].figth); } for(i=0;i<m;i++) { scanf("%d%d",&v[i].money,&v[i].shai); } sort(p,p+n,cmpp); sort(v,v+m,cmpv); if(p[0].figth>=v[0].shai) //当怪兽的最大防御力大于等于技能的最大伤害值，不可能消灭全部怪兽 { printf("-1\n"); continue; } else { fill(&ans[0][0],&ans[0][0]+maxm*15,INF); //初始每种怪兽都需要消耗无穷大晶石数目，因为是取最小值 for(i=0;i<=10;i++) ans[0][i]=0; //当怪兽的生命值为0时，消耗0晶石 for(i=1;i<=1000;i++) { for(j=0;j<=10;j++) { for(k=0;k<m;k++) { int s=v[k].shai; if(s>=i+j) s=i; else { if(s<=j) s=0; else s-=j; } //因为i-s不能<0,所以进行判断赋值，i-s相当于怪兽被技能攻击还剩余的生命值 ans[i][j]=min(ans[i][j],ans[i-s][j]+v[k].money); } } } long long sum=0; for(i=0;i<n;i++) sum+=ans[p[i].live][p[i].figth]; //加上每种怪兽需要消耗的最小晶石数目 printf("%I64d\n",sum); } } return 0; }