参考题解:
https://www.acwing.com/solution/content/237424/
主要补充自己的理解和C++代码
设 $f(l, r)$ 表示在区间 $[l, r]$ 上, 双方都采用最优策略, 先手减去后手获得分数的差值,
(先手指的当前进行选择的人, 后手指当前不进行选择的人)
记总分为 $S$ , 设按照最优策略, 先手在 $[1, n]$ 上获得 $x$ 分, 后手获得 $y$ 分 , 由 $f$ 定义:
$$
x+y=S\\
x-y=f(1,n)
$$
解得
$$ x=(S+f(1, n))\div 2\\ y=(S-f(1, n))\div 2 $$
所以问题的关键是求出 : $f(1, n)$
我们并不关心策略本身, 我们只需要知道, $f(1,n)$ 表示的一定就是按照最优策略, 在区间 $(1, n)$ 内选择时, 先手减去后手的分数差
可以按照先手第一步选择那边分为两类: 先选左边或者选右边
设现在有 A, B 两个玩家, A此时进行选择, 为先手
A选左边
则A获得 $w(l)$ 分, B变为先手, A变为后手, 因为 $f(l+1, r)$ 表示 此时先手(B) - 此时后手(A)
的分数的差值, 所以要表示 A-B分数的差值, 即为: $-f(l+1, r)$
状态转移:
$f(l, r)=w(l)-f(l+1, r)$ : A, B 在区间 $(l,r)$ 上的差值 f(l, r)
$=$ A, B 在区间 $(l+1, r)$ 上的差值 -f(l+1, r)
$+$ A选择 $l$ 后增加的值 w(l)
同理可得
A选择右边
状态转移:
$f(l, r)=w(r)-f(l, r-1)$
所以 $f(l, r)$ 应该在两类中取最大:
$f(l, r)=max(w(l)-f(l+1, r),\; w(r)-f(l, r-1))$
初始化: $f(l, l)=w(l)$ : 在区间 $(l, l)$ 上, 先手 $-$ 后手的差值为 $w(l)-0$
然后我们从小到大枚举所有区间 $(l, r)$ 即可
C++ 代码
void solve() {
cin>>n;
for(int i=1; i<=n; i++)
cin>>w[i],
f[i][i]=w[i],
sum+=w[i];
for(int len=1; len<=n; len++)
for(int l=1; l+len-1<=n; l++) {
int r=l+len-1;
//先手要使自己的分数最大化
f[l][r]=max(w[l]-f[l+1][r], w[r]-f[l][r-1]);
}
cout<<(sum+f[1][n])/2<<' '<<(sum-f[1][n])/2;
}
写的超棒,y总视频里没听明白的,在这里看懂了