PKU 1042 Gone Fishing
http://poj.org/problem?id=1042
n個の湖で釣りをする。
持ち時間はh時間あり、湖は1〜nまで順番に移動していく。(最後まで行かなくても可)
このとき、湖i〜i+1に移動するのにはti*5分かかり、湖iで釣り始めて最初の5分はfi匹釣ることが出来る。
5分釣り続けるごとに取れる魚がdi匹ずつ減っていく。
このとき、与えられた時間で魚を釣ることができる最大の匹数と、そのときの釣りの過程を表示しろというような問題。
dp+経路復元的な問題。
配列をdp[25][12*16]までしか確保していなくてめちゃくちゃWAりました。
int fi[25],di[25],ti[25],sti[25]; int dp[25][13*16]; main(){ int n; bool nf=false; while(cin>>n,n){ if(nf)cout<<endl; nf=true; int h; cin>>h; rep(i,n)cin>>fi[i]; rep(i,n)cin>>di[i]; rep(i,n-1){ cin>>ti[i]; sti[i+1]=sti[i]+ti[i]; } memset(dp,0,sizeof(dp)); int ans=0; rep(i,n){ for(int st=sti[i];st<=h*12;++st){ if(i)dp[i][st]=max(dp[i][st],dp[i-1][st-ti[i-1]]); int tp=fi[i]; int sp=0; if(i)sp=dp[i-1][st-ti[i-1]]; for(int et=st+1;et<=h*12;++et){ dp[i][et]=max(dp[i][et],max(tp,0)+sp); sp+=max(tp,0); tp-=di[i]; } } } rep(i,n)rep(j,h*12+1)ans=max(ans,dp[i][j]); vector<int>tim; rep(s,n){ if(ans==dp[s][h*12]){ int ct=h*12; rep(i,n-s-1)tim.pb(0); for(int ns=s-1;ns>=0;--ns){ for(int nt=ct-ti[ns];nt>=0;--nt){ int tp=0; for(int i=0;nt+i+ti[ns]<ct;++i)tp+=max(fi[ns+1]-di[ns+1]*i,0); if(dp[ns][nt]+tp==dp[ns+1][ct]){ tim.pb(ct-nt-ti[ns]); ct=nt; break; } } } tim.pb(ct); break; } } while(SZ(tim)<n)tim.pb(0); reverse(ALL(tim)); rep(i,SZ(tim)){ if(i)cout<<", "; cout<<tim[i]*5; } cout<<endl; cout<<"Number of fish expected: "<<ans<<endl; } }