3713514_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int n, m;
int d[10001];
int best[10002];
int sum[10001];

int main()
{
	int i, j, t, tmp;

	scanf("%d%d", &n, &m);
	sum[0] = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &d[i]);
		sum[i + 1] = sum[i] + d[i];
	}
	if (n == 1)
	{
		puts("0");
		return 0;
	}
	best[n] = best[n + 1] = 0;
	for (i = n - 1; i > 0; i--)
	{
		best[i] = 0;
		for (j = 1; j <= m; j++)
		{
			t = i + j * 2 - 1;
			if (t > n)
				break;
			tmp = best[t + 1] + sum[t - j] - sum[i - 1];
			if (tmp > best[i])
				best[i] = tmp;
		}
	}
	printf("%d\n", best[1]);
	return 0;
}