PKU 2385 Apple Catching
http://poj.org/problem?id=2385
りんごの木、1と2があって、t分間に1分間隔でどちらかの木からりんごが落ちてくる。
どちらかのりんごの木の下にいるとき、その木から落ちてくるりんごは必ず取れるものとする。
このとき、木1と木2の間を移動する回数がw回以下の制限されているもとで、取れるりんごの個数の最大値を求めるという問題。
動的計画法、dp[i][j][k]=i分までにj回以内の移動回数で、kのりんごの樹の下にいるときに取れる最大のりんごの数、というような感じで解きました。
int dp[1001][32][2]; int in[1000]; main(){ int t,w; cin>>t>>w; rep(i,t){ cin>>in[i]; --in[i]; } int ans=0; rep(i,t){ rep(j,w+1){ int tans=0; dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+(in[i]==0)); dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]+(in[i]==1)); dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][1]+(in[i]==0)); dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j][0]+(in[i]==1)); dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j+1][0]+(in[i]==0)); dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j+1][1]+(in[i]==1)); tans=max(tans,dp[i+1][j][0]); tans=max(tans,dp[i+1][j][1]); ans=max(ans,tans); } } cout<<ans<<endl; }