济南小程序网站制作,关键词百度云,3d效果图设计制作,小网站开发成本Luogu - CF859C
Analysis
由题意知每个人选择时都是以最佳情况来选#xff0c;最佳情况是指他的选择能使后面拿的更多。所以决定最佳情况是来自后面。
还有一个重要性质#xff0c;不管是 Bob 还是 Alice#xff0c;只要是拥有决策权的人面对同一个局面#xff0c;其得到…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_{i1,n}-f(i1,n)a_i sumi1,n−f(i1,n)ai。 意思是 [ i 1 , n ] [i1,n] [i1,n] 区间的和减去后面的人可以取到的最大值再加上当前可以拿的 a i a_i ai。 他选当前的数选后面的。相当于放弃了收益但保留选择权。转移到 f ( i 1 , n ) f(i1,n) f(i1,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_{i1},\ sum_{i1,n}-f_{i1}a_i\} fimax{fi1, sumi1,n−fi1ai}
我们知道第一个选的是 Bob所以 Bob 得到的就是 f 1 f_1 f1Alice 得到的就是 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 longvector 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]/*i1~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谢谢大家
