HDU 3008（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int magic[105]; int attack[105]; int dp[105][105]; int main() { int n,t,q; while(scanf("%d%d%d",&n,&t,&q)) { memset(dp,0,sizeof(dp)); if(n==0&&t==0&&q==0) return 0; int time; time=100/q; if(100%q!=0) { time+=1; } int i,j,k; for(i=1;i<=n;i++) { scanf("%d%d",&magic[i],&attack[i]); } for(i=0;i<=time;i++) { for(j=0;j<=100;j++) { dp[i][j]=99999999; } } int Max=99999999; dp[0][100]=100; for(i=0;i<time;i++) { for(j=1;j<=100;j++) { if(dp[i][j]==99999999) continue; int x; x=j+t; x=min(100,x); dp[i+1][x]=min(dp[i][j]-1,dp[i+1][x]); if(dp[i+1][x]<=0) Max=min(Max,i+1); for(k=1;k<=n;k++) { if(magic[k]>j) continue; x=j-magic[k]+t; x=min(100,x); dp[i+1][x]=min(dp[i+1][x],dp[i][j]-attack[k]); if(dp[i+1][x]<=0) Max=min(Max,i+1); } } } if(Max>time) printf("My god\n"); else printf("%d\n",Max); } return 0; }