题解：CF859C Pie Rules^_^

思路：

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

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

根据样例分析：

CPP

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

CPP

#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;
}

题解：CF859C Pie Rules^_^

文章操作

相关推荐

评论

题解：CF859C Pie Rules^_^