题目分析:参考http://www.cnblogs.com/slon/archive/2012/07/29/2614380.html
一开始感觉像贪心题,就是不知道怎么贪心,,,赛完后,牛说是dp,经典类型的dp,dp[i][j]表示建造前k条船时,伤了i生命值,当前攻击力为j时所用的最小时间,,,,
dp[i][j]=min(dp[i][j], dp[i-t[k]*(j-l[k])][j-l[k]]);
注意答案:因为建到一定程度就可以不用再建了,或者再怎么建时间也不够了,而这时候高度还没有达到L。。
所以ans 要在所有的dp[][]中查找, 而且(L-i)%j!=0时,ans++......
代码:
#include<iostream> #include<cstdio> #include<memory.h> using namespace std; int dp[1000][1000];//伤了i血量,当前的攻击力为j时,所用的最小时间 int t[1000],l[1000]; const int MAX=1000; const int inf=1000000000;//10000000000错了 int main() { int N,L; while(scanf("%d %d",&N,&L)!=EOF) { for(int i=0;i<N;i++) { scanf("%d %d",&t[i],&l[i]); } for(int i=0;i<1000;i++)//初始化 for(int j=0;j<1000;j++) dp[i][j]=inf; dp[0][0]=0; for(int i=0;i<=L;i++) for(int j=0;j<=MAX;j++)//换成L, 就WA了 for(int k=0;k<N;k++) if(j>=l[k] && i>=t[k]*(j-l[k])) { dp[i][j]=min(dp[i][j],dp[i-t[k]*(j-l[k])][j-l[k]]+t[k]); } int ans=inf; for(int i=0;i<=L;i++) for(int j=1;j<=MAX;j++)//不能换成L { int temp=0; if((L-i)%j!=0) temp++; ans=min(ans,dp[i][j]+(L-i)/j+temp); } printf("%d\n",ans); } //system("pause"); return 0; }