InputThe first line contains an integer TT
(1≤T≤101≤T≤10
), the number of the test cases.
For each test case:
the first line contains a numbers nn
(1≤n≤200001≤n≤20000
);
the second line contains n numbers: V1,V2…VnV1,V2…Vn
. (?100000≤Vi≤100000?100000≤Vi≤100000
)
OutputFor each test case, print a single number in a line: the difference between the total value of gems Alice took and the total value of gems Bob took.
Sample Input
1 3 1 3 2
Sample Output
4
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int N = 20000 + 10;
const int K = 210;
const int TN = 255 + 10;
const int MOD = 255;
int T, n;
int v[N], pre[N], dp[2][TN][K];
int main()
{
scanf("%d", &T);
while(T-- && scanf("%d", &n)!=EOF)
{
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d", &v[i]);
pre[i] = pre[i-1] + v[i];
}
int lmt = sqrt(n*2.0) + 1;
for(int idx=n;idx;idx--)
for(int k=lmt;k;k--)
{
if(idx+k <= n) {
dp[0][idx&MOD][k] = pre[idx+k-1] - pre[idx-1] +
max(dp[1][(idx+k)&MOD][k], dp[1][(idx+k+1)&MOD][k+1] + v[idx+k]);
dp[1][idx&MOD][k] = -pre[idx+k-1] + pre[idx-1] +
min(dp[0][(idx+k)&MOD][k], dp[0][(idx+k+1)&MOD][k+1] - v[idx+k]);
}
else if(idx+k-1 <= n) {
dp[0][idx&MOD][k] = dp[1][(idx+k)&MOD][k] + pre[idx+k-1] - pre[idx-1];
dp[1][idx&MOD][k] = dp[0][(idx+k)&MOD][k] - pre[idx+k-1] + pre[idx-1];
}
}
printf("%d\n", dp[0][1][1]);
}
}
原文：http://www.cnblogs.com/--lr/p/7587333.html