pku1976.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 50010
int v[size];
int dp[4][size];

int Max(int x, int y)
{
	return x > y ? x : y;
}
void Solve()
{
	int i, p, N, m, j;
	v[0] = 0;
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
	{
		scanf("%d", &p);
		v[i] = v[i - 1] + p;
	}
	scanf("%d", &m);
	if (m * 3 >= N)
	{
		printf("%d\n", v[N]);
	}
	else
	{
		memset(dp, 0, sizeof(dp));
		for (j = 1; j <= 3; j++)
		{
			for (i = m * j; i <= N; i++)
			{
				dp[j][i] = Max(dp[j][i - 1], dp[j - 1][i - m] + v[i] - v[i - m]);
			}
		}
		printf("%d\n", dp[3][N]);
	}
}

int main()
{
	int tt;
	scanf("%d", &tt);
	while (tt--)
	{
		Solve();
	}
	return 0;
}