2219.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 31 行

/*  This Code is Submitted by wywcgs for Problem 2219 on 2006-04-26 at 12:30:08 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PCN = 51200;

int main()
{
	int sum[PCN], can[4][PCN], n, mpn;
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n); sum[0] = 0;
		for(i = 1; i <= n; i++) {
			int pn; scanf("%d", &pn);
			sum[i] = sum[i-1]+pn;
		}
		scanf("%d", &mpn);
		memset(can, 0, sizeof(can));
		for(i = 1; i <= n; i++)
			for(j = 1; j <= 3; j++)
				if(i <= j*mpn) can[j][i] = sum[i];
				else can[j][i] = max(can[j][i-1], sum[i]-sum[i-mpn]+can[j-1][i-mpn]);
		printf("%d\n", can[3][n]);
	}
	
	return 0;
}