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;
  }
}