#include "head.h" /*

先手最高得分

有N张卡牌堆成一摞，每张卡牌上都会有一个整数标记其分数。

现有两个人要交替从牌堆顶拿牌，每次至少拿一张，至多拿M张，直到牌堆被拿完。

每个人拿至手中的牌的分数和即为其最终得分。假设两个人都会采取最佳策略拿牌来使自己的得分最大化，请问先手拿牌的人的得分为多少？

输入描述

输入第一行是样例个数；

对于每个样例，第一行是N，M，第二行有N个整数，代表牌堆顶到牌堆底N张牌的分数。

0 < N, M < 1,000,000, 每张牌的分数在-100和100之间

输出描述

每个样例，输出一个整数代表先手得分。

示例1

输入

2

4 2

1 1 1 1

5 2

3 -4 1 1 7

输出

2

6

说明

第一个样例，先手拿2张1，最高得分为2。 第二个样例，先手拿3，-4，逼迫对方接下来只能拿1，1，最后自己再拿到7，所以先手最高得分为6。 */

#define K 1000100
int a[K];
int f[K][2];
int main()
{
	int m, n;//n个数 m张牌
	while (cin >> n >> m){
		memset(f, 0, sizeof f);
		//cout << n << ' ' << m << endl;
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		
		int cnt_sum = 0;

		for (int i = n; i >= 1; i--){
			cnt_sum += a[i - 1];
			int sum = 0;
			for (int j = 0; i + j-1<n  && j < m; j++){
				//cout << j << endl;
				sum += a[i + j - 1];
				//f（i,0）从i到n号牌中，拿到i号牌选手最大得分
				//f（i,1）从i到n号牌中，没拿到i号牌选手的得分
				f[i][0] = max(f[i + j + 1][1] + sum, f[i][0]);
				f[i][1]= cnt_sum - f[i][0];

			}
			//cout << f[i][0] << ' ' << f[i][1]<<endl;
		}
		cout << f[1][0] <<endl;
	}

	return 0;
}

0 < N, M < 1,000,000 这样做不知道对不对，但是超时是一定的了。 求助各位大佬有没有不超时的解法？