CCC 2007 stage1 senior5 「Bowling for Numbers」

Solution of this task:DP(dynamic programming).

the recurrence formula would be as follows.

dp[i][j] := max(dp[i-1][j],dp[i-w][j-1]);

dp[i][j] means the maximum achievable score when player threw j balls and knock over no more than i pins.

computational complexity is O(nk).

japanese is here:
簡単な教育的DP
バカなのでセグフォった。
この問題level5で、level5は"the teacher will get this after many days, or maybe never :-)"って書いてあるんだけど全然そんなことない

#include <bits/stdc++.h>
using namespace std;

int n,k,w,ans;
int sum[30005],dp[30009][510];
int d[30005];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&k,&w);
		ans = 0;
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= k;j++)
				dp[i][j] = 0;

		for(int i = 1;i <= n;i++) scanf("%d",&d[i]);
		int gou = 0;
		for(int i = 1;i <= n;i++){
			gou += d[i];
			if(i > w)gou -= d[i-w];
			sum[i] = gou;
		}

		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= k;j++){
				dp[i][j] = max(dp[i-1][j],dp[max(0,i-w)][j-1]+sum[i]);
				ans = max(dp[i][j],ans);
			}
		}	
		printf("%d\n",ans);
	}
	return 0;
}