Game of Sum
题意：有一个长度为n的整数序列，两个人$A$和$B$轮流取数，$A$先取。一个玩家每次只能从左端或者右端取任意数量连续的数，但不能两边同时取。当所有的数都被取走时游戏结束，然后统计每个人取走的数的和，作为各自的得分。两个人采取的策略都是让自己得分尽可能高，并且两个人都很机智，求$A$的得分$-B$的得分后的结果。
显然，最后整数序列的所有元素必定被$A$或$B$取得。
定义：$dp[i][j]$为第i到j个数，先手能取得的最大得分,$Sum(i,j)$表示$i$到$j$的数的和。
因为彼此都很聪明，所以$dp[i][j]=Sum(i,j)-$后手所能取得的分数的最大值。而先手能从左端或右端取任意数量的数，因此：
转移方程：$dp[i][j]=Sum(i,j)-min(dp[i+1][j],dp[i+2][j],\cdots dp[j][j],dp[i][j-1],dp[i][j-2],\cdots dp[i][i])$（当先手取了第$i$个数，此时的后手得分就是$dp[i+1][j]$，其他以此类推)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
class Computer {
array<int, 101> Data;
array<int, 101> PrefixSum;//前缀和，用于求Sum(i,j)
array<array<int, 101>, 101> Dp;
array<array<bool, 101>, 101> Vis;
int n;
Computer() = default;
void Init()noexcept{
for_each(Vis.begin(), Vis.end(), [](array<bool, 101> & Array)->void {
Array.fill(false);
});
for_each(Dp.begin(), Dp.end(), [](array<int, 101> & Array)->void {
Array.fill(0);
});
PrefixSum[1] = Data[1];
for (int i = 2; i <= n; ++i) {
PrefixSum[i] = PrefixSum[i - 1] + Data[i];
}
}
int Dfs(int From, int To) {
if (Vis[From][To]) {
return Dp[From][To];
}
Vis[From][To] = true;
int&& M = 0;
for (int i = From + 1; i <= To; ++i) {
M = min(M, Dfs(i, To));
}
for (int i = From; i < To; ++i) {
M = min(M, Dfs(From, i));
}
return (Dp[From][To] = PrefixSum[To] - PrefixSum[From - 1] - M);
}
public:
static Computer computer;
bool Input() {
cin >> n;
if (!n) {
return false;
}
for (int i = 1; i <= n; ++i) {
cin >> Data[i];
}
return true;
}
int getAns() {
Init();
int&& Temp = Dfs(1, n);
return Temp - (PrefixSum[n] - Temp);
}
};
Computer Computer::computer;
int main() {
while (Computer::computer.Input()) {
cout << Computer::computer.getAns() << endl;
}
return 0;
}
