P2964-[USACO09NOV]A Coin Game S
题目:
题目描述:
小 A 和小 B 在玩游戏。
初始时，有 $n$ 个硬币被摆成了一行，从左至右第 $i$ 个硬币的价值为 $c_i$。
游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币，那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 $2$ 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
输入格式:
输入的第一行是一个整数 $n$，代表硬币的个数。
第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。
输出格式:
输出一行一个整数，代表小 A 能获得的最大累计价值。
样例:
样例输入 1:
样例输出 1:
思路:
实现:
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;
}
|