题解：CF859C Pie Rules^_^

· · 题解

思路：

容易发现 Bob 得分一定比 Alice 高，所以我们只需要考虑当 Alice 用最优策略时 Bob 的最高得分，Alice 的得分就是总数减去 Bob 的得分。

思考什么情况下会给对方，什么情况下会给自己。

根据样例分析：

3
141 592 653

若 Bob 把 141 给到 Alice，那么他也会把 592 给 Alice，因为他选 653 比选 592 更优。但即便如此，Alice 得到了 733，即 a_1+a_2。所以 Bob 必须选 141。

通过以上分析，我们发现不易确定当前这一步选的在下一步是否最优，也就是有后效性，所以正难则反，设 f_i 表示从 i 到 n 的最优值。

如果选这个值，那么下一个位置的决策就给了 Alice，那么 f_{i+1} 就会给 Alice。我们对于 Bob 来讲，就相当于减去了 f_{i+1}，这时的 f_i 就是第 i 个数到第 n 个数的和，所以再维护一个前缀和就行了。

如果不选这个值，那么就等于 f_{i+1}

设 b_i 表示从 i 到 n 的后缀和，则状态转移方程为：

f_i=\max(f_{i+1},b_i-f_{i+1})

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,a[55],sum[55],f[55];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=n; i>=1; i--) sum[i]=sum[i+1]+a[i];
    for(int i=n; i>=1; i--) f[i]=max(f[i+1],sum[i+1]-f[i+1]+a[i]);
    cout<<sum[1]-f[1]<<' '<<f[1];
    return 0;
}