[USACO09NOV] A Coin Game S
题目背景
题目描述
小 A 和小 B 在玩游戏。
初始时，有 n n n 个硬币被摆成了一行，从左至右第 i i i 个硬币的价值为 c i c_i ci。
游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 k k k 个硬币，那么本次自己最多取出 k × 2 k \times 2 k×2 个硬币。当没有硬币可取时，游戏结束。
游戏开始时，由小 A 先动手取硬币，最多取出 2 2 2 个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。
输入格式
输入的第一行是一个整数 n n n，代表硬币的个数。
第 2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行，每行一个整数，第 ( i + 1 ) (i + 1) (i+1) 行的整数代表第 i i i 个硬币的价值 c i c_i ci。
输出格式
输出一行一个整数，代表小 A 能获得的最大累计价值。
样例 #1
样例输入 #1
5
1
3
1
7
2
样例输出 #1
9
提示说明
输出输出样例 1 1 1 解释
初始时，硬币序列为 { 1 , 3 , 1 , 7 , 2 } \{1,~3,~1,~7,~2\} {1, 3, 1, 7, 2}。
由小 A 先操作，他取出了一个硬币，硬币序列变为 { 3 , 1 , 7 , 2 } \{3,~1,~7,~2\} {3, 1, 7, 2}，小 A 的累计价值为 1 1 1。
再由小 B 操作，由于小 A 上回合取出了 1 1 1 个硬币，所以他本回合可以取出至多 1 × 2 = 2 1 \times 2 = 2 1×2=2 个硬币。他取出了一个硬币，硬币序列变为 { 1 , 7 , 2 } \{1,~7,~2\} {1, 7, 2}，小 B 的累计价值为 3 3 3。
再由小 A 操作，由于上回合小 B 取出了 1 1 1 个硬币，所以他本回合可以取出至多 1 × 2 = 2 1 \times 2 = 2 1×2=2 个硬币。他取出了两个硬币，硬币序列变为 { 2 } \{2\} {2}，小 A 的累计价值为 1 + 1 + 7 = 9 1 + 1 + 7 = 9 1+1+7=9。
再由小 B 操作，由于上回合小 A 取出了 2 2 2 个硬币，所以他本回合可以取出至多 2 × 2 = 4 2 \times 2 = 4 2×2=4 个硬币。但是只剩下了 1 1 1 个硬币，因此他只能取出一个硬币，硬币序列变为空，小 B 的累计价值为 3 + 2 = 5 3 + 2 = 5 3+2=5，游戏结束。
数据范围与约定
对于全部的测试点，保证 5 ≤ n ≤ 2 × 1 0 3 5 \leq n \leq 2 \times 10^3 5≤n≤2×103， 1 ≤ c i ≤ 1 0 5 1 \leq c_i \leq 10^5 1≤ci≤105。
提示：请注意本题的空间限制为 20 20 20 MiB。
代码内容
// #include <iostream>
// #include <iomanip>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e3+10;
int s[N],dp[N][N];
int main()
{
ll n;
cin>>n;
for(ll i=n;i>=1;i--)
cin>>s[i];
for(ll i=1;i<=n;i++)
s[i]+=s[i-1];
for(ll i=1;i<=n;i++)
for(ll j=1,k=2*j-1;j<=n;j++,k=2*j-1)
{
dp[i][j]=dp[i][j-1];
if(k<=i) dp[i][j]=max(dp[i][j],s[i]-dp[i-k][k]);
if(k+1<=i) dp[i][j]=max(dp[i][j],s[i]-dp[i-k-1][k+1]);
}
cout<<dp[n][1]<<endl;
return 0;
}