省流：全是记忆化……
T1
想了 \(30\ min\)，突然想出来了。
设 \(f[i][j]\) 表示将第 \(i\) 个的前 \(j\) 个变成好串的最小代价。
核心代码：
f[i][j]=min(f[i-k][j-k]+f[i][k],f[i][j]);
需要预处理，但是第一发 T 了。
将预处理优化为：
f[i][j]=f[i-2][j-4]+(s[l]==s[r]?0:min(w[l],w[r]))+(s[l+1]==s[r-1]?0:min(w[l+1],w[r-1]));
可过。
T2
神奇小性质：只要有一种情况胜利，那么就有必胜策略。
然后加个记忆化就过了。
T3
暴力枚举交换哪两个字符，加个记忆化 \(35\ pts\)。
然后 DFS 变成 BFS 有 \(50\ pts\)，但是我 \(45\ pts\)。
正解是 DP ……
T4
输出 \(-1\) 有 \(18\ pts\)。
但是没看到特殊性质……
正解是记忆化……
标签：26,专题,min,正解,2024.7,记忆,pts From： https://www.cnblogs.com/whrwlx/p/18339318