CF 859C - Pie Rules（dp好题）

【DP】CF859C Pie Rules

https://www.luogu.org/problemnew/show/CF859C

Description

有一个长度为n的序列，Alice和Bob在玩游戏。Bob先手掌握决策权。

他们从左向右扫整个序列，在任意时刻，拥有决策权的人有如下两个选择：

将当前的数加到自己的得分中，并将决策权给对方，对方将获得下一个数的决策权

将当前的数加到对方的得分中，并将决策权保留给自己，自己将获得下一个数的决策权

假定他们都使用最优策略，求他们最后分别能获得多少分

Input

第一行是一个整数n代表序列长度

第二行有n个用空格隔开的整数，代表这个序列

Output

输出一行两个用空格隔开的整数，代表Alice和Bob的最终得分

Hint

Forall:

0 ≤ n ≤ 50。

若设序列为a，则1 ≤ ai ≤ 100000

Solution

傻逼数据范围给了50……看着题目想折半搜索想了半天，搜了下题解发现是O(n)的DP……那你给我50的范围是要干嘛啊emmmm

考虑正着dp，设fi为前i个数的ans，于是发现并不能转移，因为填表转移时是对手和你一起决策，一个取max一个取min显然没法做。填表法并不能记录这个状态是先手的还是后手的，记录先后手也不能做。

于是考虑倒着做，设fi为从i开始选一直选到n，发现这样的决策是自己一个人做最优决策，转移到下一维的最大值即可。方程显然：

fi = max(fi+1 ,sumi−fi+1)

其中sum代表后缀和

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
int a[maxn];
int dp[maxn], sum[maxn];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  } 
  //dp[i] 表示 i-n先手的最优决策
  //如果当前位置不选择，选择权还在自己 使用 dp[i] = dp[i + 1]
  //如果 当前位置不选择，选择权给对方,所以dp[i + 1] 是对方的最优决策 自己的最优决策 时sum[i + 1] - dp[i + 1] + a[i]
  for (int i = n; i >= 1; i--) {
    sum[i] = sum[i + 1] + a[i];
    dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);
  }
  cout << sum[1] - dp[1] << " " << dp[1] << endl;
  return 0;
}