区间dp入门选讲
合并果子
传送门
设 \(f_{i,j}\) 表示合并区间 \([i,j]\) 的最小代价， \(\begin{aligned}s_i=\sum^{i}_{k=1}a_k\end{aligned}\) ，显然有 \(\begin{aligned}f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}+s_j-s_{i-1})\end{aligned}\) 。
括号匹配
题意：给出一个只有 ()[] 四种字符组成的字符串，取出一个最长的子序列使得他们满足括号匹配，求最长匹配长度。
设 \(f_{i,j}\) 表示区间 \([i,j]\) 内的最长匹配长度。若 \(\begin{aligned}s_i=s_j\end{aligned}\) ，则直接累加 \(\begin{aligned}f_{i,j}=f_{i+1,j-1}+2\end{aligned}\) 。对于一般情况可以直接合并，即有， \(\begin{aligned}f_{i,j}=\max(f_{i,j},f_{i,k}+f_{k+1,j})\end{aligned}\) 。
Palindrome
传送门
题意：给定一个字符串 S ，问需要至少插入几个字符能使其变为回文串。 \(|S|\le5000\) 。
设 \(f_{i,j}\) 表示使区间 \([i,j]\) 变成回文串的最小插入次数，考虑简单分类讨论，则有 \(f_{i,j}=\left\{\begin{matrix}
f_{i+1,j-1}&iff&s_i=s_j\\
\min(f_{i+1,j},f_{i,j-1})+1&iff&s_i\neq s_j
\end{matrix}\right.\) 。注意此时枚举状态时，我们令 \(i:n\sim1,j:i\sim n\) 。
Again Palindrome
传送门
题意：给定一个字符串 S ，问有几种删字符的方案能使其变为回文串（不删也是一种方案，但全删不可以）。 \(|S|\le5000\) 。
设 \(f_{i,j}\) 表示删字符后使区间 \([i,j]\) 变为回文串的方案数。若 \(s_i\neq s_j\) ，简单容斥一下就好；若 \(s_i=s_j\) ，考虑 \(f_{i+1,j}+f_{i,j-1}\) 会将中间的 \([i+1,j-1]\) 的部分算两遍，但因为 \(s_i=s_j\) ，故会增加 \(f_{i+1,j-1}\) 种方案，因为本身 \([i+1,j-1]\) 的部分已经是回文了，此时还有一个特例，即 \([i+1,j-1]\) 全删，而字符串 \([s_is_j]\) 同样是回文串，故再加一。于是得到方程： \(f_{i,j}=\left\{\begin{matrix}
f_{i+1,j}+f_{i,j-1}+1&iff&s_i=s_j\\
f_{i+1,j}+f_{i,j-1}-f_{i+1,j-1}&iff&s_i\neq s_j
\end{matrix}\right.\) 。
String painter
传送门
题意：给定字符串 A 和 B，每次操作可以把一个区间变成同一个字符，问最少需要多少次操作能把 A 变成 B 。 \(|A|,|B|\le100\) 。
设 \(f_{i,j}\) 表示 \([A_i...A_j]\) 变为 \([B_i...B_j]\) 的最少操作数。考虑直接这样做转移很麻烦，于是我们先考虑怎么从空串变成 B 。设 \(g_{i,j}\) 表示空串变为 \([B_i...B_j]\) 的最少操作数。
考虑如果 \(B_{i}=B_{i+1}\) 则显然在涂色时，可以由 \([i+1,j]\) 直接向左扩展为 \([i,j]\) ，而 \(B_j=B_{j-1}\) 或 \(B_i=B_j\) 时同理。于是不难得到方程：\(g_{i,j}=\left\{\begin{matrix}
\min(g_{i,j},g_{i+1,j})&iff&B_i=B_{i+1}&or&B_i=B_j\\
\min(g_{i,j},g_{i,j-1})&iff&B_j=B_{j-1}&or&B_i=B_j
\end{matrix}\right.\) 。
然后我们考虑由 \(g_{i,j}\) 为踏板来转移 \(f_{i,j}\) 。此时我们可以改设 \(f_i\) 表示从 \([A_1...A_i]\) 变为 \([B_1...B_i]\) 的最小操作数。
考虑先枚举 \(i\) ，若 \(A_i=B_i\) ，则不需要涂色，直接继承上一状态；若 \(A_i\neq B_i\) ，则枚举 \(j\) 表示从 \(j\) 处开始往后刷，使得 \(f_{j}+g_{j+1,i}\) 最小。于是不难得到方程： \(f_{i}=\left\{\begin{matrix}
\min(f_i,f_{i-1})&iff&A_i=B_i\\
\min(f_i,f_{j}+g_{j+1,i})&iff& A_i\neq B_i
\end{matrix}\right.\) 。
搬寝室
传送门
题意：有 \(n\) 个行李，每个行李有一个重量。现在你要通过 \(k\) 次操作搬走 \(2k\) 个行李。每次左右手各拿一个行李，其重量分别为 \(x\) 和 \(y\) 。每次操作的疲劳度为 \((x-y)^2\) ，要求最小化疲劳度。 \(2\le 2k\le n<2000\) 。
首先注意到一个显然的贪心策略，即对每个行李排序后，要选取的必然是相邻的两个行李。设 \(f_{i,j}\) 表示前 \(i\) 个行李中选取了 \(j\) 组行李的最小疲劳度。每次我们考虑选或不选。若选，则要选第 \(i\) 和第 \(i-1\) 个行李且此时要满足在前 \(i-2\) 个行李中已经选取了 \(j-1\) 组行李。于是不难得出方程：\(\begin{aligned}f_{i,j}=\min(f_{i-1,j},f_{i-2,j-1}+(a_i-a_{i-1})^2)\end{aligned}\) 。
配对
传送门题意：有一个长度为 \(n\) 的序列，每个数都是 \(1\sim K\) 中的整数。现在有一些位置的数被遮住了，用 \(-1\) 表示。你可以往这些位置中填入 \(1\sim K\) 中的数，要求最小化逆序对数。 \(1\le n\le10000,1\le K\le 100\) 。
首先注意到一个显然的贪心策略，即我们考虑填入的数肯定是单调不降的。考虑如果填入的数 \(a_i>a_j(i<j)\) ，则会在填入的数中产生额外的逆序对，可以证明这样是不优的。
设 \(f_{i,j}\) 表示当前填到前 \(i\) 个未知位且第 \(i\) 个未知位上填的数为 \(j\) 的逆序对数，设 \(g_{i,j}\) 表示 \(a[1...i-1]\) 中大于 \(j\) 的个数， \(h_{i,j}\) 表示 \(a[i+1...n]\) 中小于 \(j\) 的个数。
我们只需要考虑填入一个数后原序列会产生的贡献，故有方程 \(f_{i,j}=\min(f_{i,j},f_{i-1,k}+g_{i,j}+h_{i,j})(k\le j)\) 。最后我们再加上原数列的逆序对数即可。