小 A 和小 B 在玩游戏。
初始时，有 n 个硬币被摆成了一行，从左至右第 i 个硬币的价值为 ci。
游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 k 个硬币，那么本次自己最多取出 k×2 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 2 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
输入的第一行是一个整数 n，代表硬币的个数。
第 2 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数代表第 i 个硬币的价值 ci。
输出一行一个整数，代表小 A 能获得的最大累计价值。
1
2
3
4
5
6
7
| 5
1
3
1
7
2
|
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
| #include "ybwhead/ios.h"
const int maxn = 2e3 + 10;
int a[maxn];
int sum[maxn];
int dp[maxn][maxn];
int n;
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
yin >> a[i];
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = dp[i][j - 1];
int k = j << 1;
if (k <= i)
dp[i][j] = max(dp[i][j], sum[i] - dp[i - k][k]);
k--;
if (k <= i)
dp[i][j] = max(dp[i][j], sum[i] - dp[i - k][k]);
}
}
yout << dp[n][1] << endl;
return 0;
}
|
v1.4.14