PKU 3920 RIPOFF
http://poj.org/problem?id=3920
スタート地点からゴール地点までジャンプしながら進む。
このとき、升目に書いてある得点を得る。
最大のジャンプ回数がT、最大のジャンプ幅がSのときに、ゴールしたときの得点の最大値を求めろというような問題。
典型的なDP。
現在地とジャンプ回数を保持しました。
int dp[300][300]; int in[300]; main(){ int n,s,t; while(cin>>n,n){ cin>>s>>t; rep(i,n+2)rep(j,n+3)dp[i][j]=-(1<<28); rep(i,n)cin>>in[i+1]; in[0]=0; in[n+1]=0; dp[0][0]=0; int ans=-(1<<28); for(int i=1;i<=n+1;++i){ for(int j=1;j<=t;++j){ for(int p=max(0,i-s);p<i;++p)dp[i][j]=max(dp[i][j],dp[p][j-1]+in[i]); if(i==n+1)ans=max(ans,dp[i][j]); } } cout<<ans<<endl; } }