有n（2e4）个宝石
两个人轮流从左侧取宝石，Alice先手，首轮取1个或2个宝石，
如果上一轮取了k个宝石，则这一轮只能取k或k+1个宝石。
一旦不能再取宝石就结束。
双方都希望自己拿到的宝石数比对方尽可能多。
问你，先手比后手多拿的最大宝石数。
dp[s][k] 表示从已经拿了s个，这一次可以拿k个，也可以拿k+1个。
那么dp[s][k] 表示 已经拿了s个，这一次可以拿k个或k+1个的最大差值。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = + ;
const int INF = 0x3f3f3f3f; int a[maxn], sum[maxn];
int dp[maxn][];
int n; int DP(int s, int k)
{
if(dp[s][k] != -INF) return dp[s][k];
if (s+k <= n) dp[s][k] = max(dp[s][k], sum[s+k]-sum[s]-DP(s+k, k));
if (s+k+ <= n) dp[s][k] = max(dp[s][k], sum[s+k+]-sum[s]-DP(s+k+, k+));
if (dp[s][k] == -INF) dp[s][k] = ;
return dp[s][k];
} void init()
{
memset(sum, , sizeof(sum));
for (int i = ; i < maxn; i++)
for (int j = ; j <= ; j++)
dp[i][j] = -INF;
} int main()
{
int t;
scanf("%d", &t);
for (int ca = ; ca <= t; ca++)
{
init();
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]), sum[i] = sum[i-] + a[i];
printf("%d\n", DP(, ));
}
}