Link。
有点难想的 DP。
考虑 \(f_i\) 表示前 \(i\) 个字符的最小代价，显然有转移方程 \(f_i=\min\{f_{i-1}+a,\min_{j,k,k\ge i-j,s_{j-k+1,\cdots,j}=s_{i-k+1,\cdots,i}}f_{j}+b\}\)。
注意到复杂度是 \(O(n^3)\) 的。
感性理解可以发现 \(f\) 单调不减。
那么对于一个固定的 \(j\)，显然 \(k\) 越大一定不劣，此时 \(k\) 最大为 \(1\sim i\) 和 \(1\sim j\) 的 \(LCP\)，那么转移方程就是 \(f_i=\min\{f_{i-1}+a,f_{\max\{i-lcp_{i,j},j\}+b}\}\)。
至于为什么要取 \(\max\)，因为如果不取的话，就相当于用了还没出现的字符串。
总之，非常有趣！
Link。
考虑倒着做，考虑第 \(i\) 个位置，显然 \(i+1\sim n\) 已经满足条件了，那么对于 \(s_i=0\)，改成 \(1\) 一定不优，否则，如果后面的 \(1\) 的数量大于等于 \(0\) 的数量，那么把 \(s_i\) 改成 \(1\) 并不会使答案变大。
感性理解吧。。严谨证明并不是很会。
Link。
数据结构好题！
显然最小值很好统计，以下只考虑最大值。
考虑如何暴力做：记录数列，然后把所有的人的位置更新答案。
接下来观察每一次把一个人 \(x\) 提前，对所有的人的影响，显然除了 \(x\) 自己，其他人的排名一定上升或不变。那么正解也就呼之欲出了：我们在排名变小前并不要更新答案，另外在结束时统计答案，因为如果此时答案变大的话可以在后面一定会统计到，变小的话后面不一定统计到。
Link。
考虑一对括号 \((i,j)\)，发现删掉 \((i,j)\) 的代价为这对括号的深度（有多少对括号包含这对括号），那么移动括号可以减去 \((j-i-1)/2\) 的答案，排序一下就做完了。
组合数题。
直接做并不好做，考虑每个点会有多少点出去。
显然是 \((1,1)\) 到这个点的方案数，组合数并不难计算，但是复杂度是 \(O(n^2)\) 的。
然后拆式子可以做到 \(O(n)\)。
标签：11,括号,Link,答案,考虑,sim From： https://www.cnblogs.com/incra/p/18540597