题解：CF859C Pie Rules
Luogu - CF859C
Analysis
由题意知每个人选择时都是以最佳情况来选，最佳情况是指他的选择能使后面拿的更多。所以决定最佳情况是来自后面。
还有一个重要性质，不管是 Bob 还是 Alice，只要是拥有决策权的人面对同一个局面，其得到的最大得分一定相等。这样，我们找到了固定状态，就可以 dp 了。
因为我们管的是从某个位置往后面取的最大值，所以可以找某一个位置 i i i 到 n n n 的值。
设 f ( i , n ) f(i,n) f(i,n) 表示 i ∼ n i \sim n i∼n 区间里，选到 i i i 时，先手取的最大值。 a a a 数组存储原序列， s u m i , j sum_{i,j} sumi,j 表示 a i ∼ a j a_i \sim a_j ai∼aj 的和。
分两种情况：
-
他要拿的当前的数。相当于增加收益，但把选择权给了对方。转移到 s u m i + 1 , n − f ( i + 1 , n ) + a i sum_{i+1,n}-f(i+1,n)+a_i sumi+1,n−f(i+1,n)+ai。
意思是 [ i + 1 , n ] [i+1,n] [i+1,n] 区间的和，减去后面的人可以取到的最大值，再加上当前可以拿的 a i a_i ai。 -
他选当前的数，选后面的。相当于放弃了收益，但保留选择权。转移到 f ( i + 1 , n ) f(i+1,n) f(i+1,n)。
发现 f f f 函数第二个参数都是 n n n，可以省略。
于是，设 f [ i ] f[i] f[i] 表示先手面对 i ∼ n i \sim n i∼n 时，可以取到的最大值。
我们只需将两种情况的最大值，赋值给 f i f_i fi 即可：
f i = max { f i + 1 , s u m i + 1 , n − f i + 1 + a i } f_i=\max\{f_{i+1},\ sum_{i+1,n}-f_{i+1}+a_i\} fi=max{fi+1, sumi+1,n−fi+1+ai}
我们知道第一个选的是 Bob，所以 Bob 得到的就是 f 1 f_1 f1，Alice 得到的就是 Bob 剩下的，即 s u m 1 , n − f 1 sum_{1,n}-f_1 sum1,n−f1。
Code
考虑倒序 dp。注意 a i a_i ai 的范围是 1 0 6 10^6 106，不开 long long 必然会炸。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector <int> a(n + 1); // 原始数组vector <ll> s(n + 1); // 前缀和数组，a[i]<=1e6，开long long！vector <ll> f(n + 2); // dp数组，long longfor(int i = 1; i <= n; i ++){cin >> a[i];s[i] = s[i - 1] + a[i];}for(int i = n; i >= 1; i --){ // 倒推f[i] = max(f[i + 1], (s[n] - s[i]/*i+1~n区间和*/) - f[i + 1] + a[i]);}cout << s[n] - f[1] << ' ' << f[1] << endl;
}signed main()
{ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}
End
这里是 YLCHUP，谢谢大家！