正难则反 || solution - CF859C
littlebug
·
·
题解
## Solution
首先这种博弈论是 dp 的概率非常大，于是考虑 dp。
不过似乎很难做，因为无论怎么设计状态总是会有后效性。
那么，正难则反，既然正着 dp 很难处理，于是考虑反过来 dp！
设 $f_i$ 为轮到先手选 $i$，只考虑 $i \sim n$ 的时候的最大权值和，那么分讨选或不选，选则减去不选就直接是 $f_{i+1}$；选则把 $f_{i+1}$ 减掉，剩下的就是 $f_i$（可以后缀和优化掉）。
也就是方程（其中 $s_i$ 为后缀和数组）：
$$
f_{i} = \max (f_{i+1} , s_i - f_{i+1})
$$
于是，我们便用 $O(n)$ 的时间复杂度过了 $n \le 50$，这甚至比 $n^2$ 过百万还罕见。
## Code
```cpp
int n,a[MAXN],f[MAXN],s[MAXN];
signed main()
{
read(n),_::r(a,n);
rpe(i,n,1) s[i]=s[i+1]+a[i];
rpe(i,n,1) f[i]=max(f[i+1],s[i]-f[i+1]);
write(s[1]-f[1],f[1]);
return 0;
}
```
---
华风夏韵，洛水天依！