CF38F 题解

blog。严重怀疑这题放到 2023 年至少 *2000，评绿合情合理。

首先是博弈论。然后数据范围很小。直接暴力 DP 啪的一下上去了，很快啊！

这就抽象起来了。另一篇题解说不能暴力转移，但是你先预处理出来 \(num(s)\)，然后直接记忆化搜索，暴力枚举每一次操作的字符，这不就做完了吗。

具体一点的话，直接模拟下面过程就可以过题了。

• dfs() 传参就把题目里面有用的东西全传进去，\(s\)，\(\sum\limits_{i=1}^{|s|} \operatorname{value}(s_i)\) 与 \(\max\limits_{1\le i\le |s|}\{\operatorname{value}(s_i)\}\)。
• 你每次返回三个数，一个记录是谁的必胜态，另外两个记录先后手的分数。
• 最后 naive 地转移：能赢最重要，其次是先手的分数越大越好，然后是后手的分数越小越好。

code，时间复杂度 \(O(\text{能过})\)。