这一章是DP。本章我的代码见Github。
9.2节例题9-2 uva437
试了一下std::tuple，感觉比较麻烦。
9.2节例题9-3 uva1347
9.4节例题9-6 uva11400
9.4节例题9-8 uva1625
本来想同时存储选i,j个元素的最优结果和对应各字母的最后一个位置进行状态转移，但发现这样没有最优子结构（比如，如果目前的字母各不相同，你并不知道哪种顺序是最优的，但这可能影响后面的选择）。看了书上的解法，发现书上精妙地把复杂地状态简单化了：我只需要考虑那些还没选完的字母个数，而这是只取决于当前状态而与将来无关的。
9.4节例题9-9 uva10003
四边形不等式优化不太好理解。
●9.4节例题9-11 uva1331
做法大致同lrj标程，不同处在于我把点预先扩大了两倍然后直接用整数处理中点，最后输出答案要除以4。自闭了好长时间，第一会有精度的问题，第二我抄lrj的围绕数模板抄错了一个地方！这里坑了我好长时间，找到了数据和标程的结果一个个对才发现错误！
9.4节例题9-13 uva1220
要注意名单的顺序是随意的，可能上级的名字没出现过，这里WA了。
9.4节例题9-14 uva1218
因为开始的时候写的是0~n-1，后来改成1~n了但是初始化的部分没改，自闭了不少时间。这题溢出问题其实用long long就可以完全解决。
9.4节例题9-16 uva1252
状态压缩DP不太好理解。
9.5节例题9-18 uva10618
题目对于能量的说明比较坑……没有动作应该不消耗能量，如果这次移动的脚和上一次移动的脚不一样就只消耗1能量。这题的状态转移全用if写的，又臭又长，还好没出问题。
9.5节例题9-19 uva1627
这题不用dp做也可以，用贪心法把d值从大到小排序，每次尽量“中和”地取即可，和第8章习题8-10是一样的（那里有证明），贪心法显得简洁很多。这题重点在于将“相互认识”的条件反转变成找二分图的问题，再用dfs处理。因为输出空行的问题WA了一发。
9.5节例题9-21 uva1336
9.5节例题9-22 uva12105
本来想存储拼火柴时第一位的数字作为状态然后状态转移，发现这样并不满足dp的条件。lrj的标程提供的做法很神奇，是从右往左拼的，但是j却似乎是反过来的，还是不太理解这是怎么做的。
9.5节例题9-23 uva1204
代码写的又臭又长。主要是单独处理预处理后n==1的情形、计算重叠长度和DP。似乎不能按照书上说的用f[i][j]表示重叠最大长度，而应当直接表示拼接后的最小长度？标程似乎没有单独处理n==1的情形，是怎么做到的？反正是很迷的一道题。
9.5节例题9-25 uva12170
9.5节例题9-26 uva1380
设f[i][j]表示能否安排i的子树使得i恰好在j天完成。无根树转有根树，对于叶子节点f[i][j]=true。如果有i->k，那么f[i][j]=true当且仅当f[k][1..j-1]中至少有一个true；i<-k同理。如果是i-k，那么f[i][j]为true当且仅当f[k][1..j-1,j+1..k]至少有一个true。时间复杂度\(O(nk)\)（这里k表示最长有向链的长度。书上的做法比较难懂……但是是\(O(n)\)的。注意输入的节点之间并没有先后顺序，所以应该直接建图，然后再dfs转有根树。
9.5节例题9-28 uva1439
书上的做法太nb了。重点应该是定向问题与染色问题的等价性，然而并不会怎么证？
习题9-1 uva10285
用f[i][j][k]表示滑到(i,j)且高度不低于k的最长路径，则有不滑和从四个方向滑过来两种状态转移方式。可以用滚动数组优化空间。
习题9-2 uva10118
用f[i][j][k][l]表示四个堆各取i,j,k,l个的最多pair数，然后考虑取哪一个堆上的糖果，注意排除不可行的情况（篮子满了）。似乎和裸搜索并无太大区别？
习题9-3 uva1629
用f[i][j][k][l]表示a[i..k][j..l]所需的最小切割线数，然后考虑切的位置进行状态转移，边界条件是如果恰好有一个樱桃则f=0，如果没有就是f=INF。时间复杂度\(O(n^2m^2(n+m))\)。
习题9-4 uva1630
设f[i][j]表示s[i..j]折叠后的最小长度，考虑不做操作、分割和将s[i..j]全体折叠三种方式的状态转移。
习题9-5 uva242
设f[i][j]表示用i张邮票，是否能拼出面值为j，时间复杂度\(O(s^2na)\)（这里a表示最大的邮票面值）。网上还有一种完全背包的做法：设f[i][j]表示前i种邮票拼出1~j最少要用的邮票数量，时间复杂度\(O(sna)\)，效率更高一些（好像比我快了很多）。
习题9-6 uva10723
设f[i][j]表示s1[1..i],s2[1..j]的最短长度，g[i][j]表示对应的种类数量，状态转移类似LCS。但是当s1[i]==s2[j]的时候不能考虑另外两种状态转移，因为此时f[i-1][j-1]一定是最优的，而且其他两种对应的f即便和f[i-1][j-1]相等，对应的最短串也是一样的不能累加g。
●习题9-7 uva1631
设f[s]表示从s变为b[1..len(s)]所需的最少次数。首先注意到有以下几个论断：
- 所有的旋转操作可以任意交换次序。
- 对于以b[i]为最后一位的所有操作，他们旋转的方向相同。（假设有两个方向相反的旋转，那么我们可以把这两个旋转复合，变成1个或者2个新的旋转，所需次数不增）
于是考虑旋转最后一位，有向上转和向下转两种，再考虑同一个方向的旋转有几个3格的、几个2格的和几个1格的，利用记忆化进行dp。注意我们不能保证向上/下转的对应次数较小者一定是最优解（样例2就是，更小一点的是652 399），这里WA了。
利用map<string,int>存储dp数组。于是TLE了。
参考了网上的题解，发现可以这样优化：s除去最后2位以外其他位置都必然与a相同，故设f[n][x][y]表示a[1..n]种a[n-1]改为x，a[n]改为y，变为b[1..n]的最小次数，然后和刚刚的状态转移一样。这样就省去了string处理和map查找的开销。
习题9-8 uva1632
和例题9-21一样，容易看到经过的点形成一个区间，所以设f[i][j][k]表示经过i~j，最后停留在i(k=0)或j(k=1)的最少时间，对于不满足deadline的f设为INF。这题题意不清，对于恰好在deadline到达的情况是算失败的（借助uDebug才知道）。
习题9-9 uva10163
二分L，然后题目转化为多重背包问题，可以用单调队列优化，时间复杂度\(O(NM\log_2{L})\)（其中\(L=\max_{1\le i\le n}{P_i}\)。不过似乎不用优化也很快？而且似乎可以用01背包做？
●习题9-10 uva10641
题目对于什么算照亮的定义并没有看懂……我的做法是从光源到相邻两顶点的光线如果都在这条边的右侧（不包括共线）则算照亮否则不算，网上的题解是直接判断这两条光线叉乘的符号。
不难看出每个光源能照亮的一定是一个区间，题目转化为区间选择的问题。把n边形展开成2n条边，本来的想法是设f[a][b]表示覆盖a~b的所有边的最小费用和，每次输入一个新光源可以找到它照亮的所有区间（考虑到展开成了2n条，有2个或者3个照亮区间），然后用这些区间更新f[a][b]，但是不知道为什么总是WA。
按照网上的题解，应该先确定每个光源在2n条边中照亮的区间（如果被0割开了就选跨越n的那个区间，否则选1~n范围内的那个区间），然后枚举起点，设f[a]表示覆盖起点到i的所有边的最小费用和，再枚举选择哪个光源进行状态转移。此外按照题解做法写的时候把MAXM写成了MAXN，OJ报WA而不是RE，这里一直没调出来。
习题9-11 uva1633
设f[i][j]表示前i个字符，以j（二进制）为末k位的所有可能01串数量，只要在状态转移时排除可能的k/k+1回文子串就可以保证满足条件。因为初始化的问题WA了一次。
★习题9-13 uva1289
最先想的是先把必须要拆开来的地方（比如124，其他盘上有个3，那就必须得拆成12 4）拆开，然后从大到小一个个叠上去，但是考虑12 12不能这么做。
然后转变了一下，考虑把不同直径的部分全拆开来（相同直径的部分不应该拆开），叠回去的时候如果相邻两部分本来就属于同一堆就补偿拆开的代价。因为直径不同的部分必须有先后顺序，所以问题就变成了：有若干块盘子，每块有一个直径和一个编号，调整块的顺序使得直径不减并且相邻不同编号的块数最小。答案等于最小的这个数量*2-原来的堆数+1。
我们把所有相同直径的块放在一起，设f[i][j]表示调整前i种直径的块，并且最后以编号为j的块结尾的最优答案，状态转移是枚举前i-1种直径的块的结尾编号k，如果现在有编号为k的块那么把k放最前面可以抵消——代价为u-1（u为第i种直径块的数量），否则不管怎样都不能抵消——代价为u。
但这样WA了。我们应该特判j=k的情况：这时我们不能简单地抵消，因为如果存在j以外的块(u>1)，要么我们把j拆开来——和k能抵消，但是拆开本身又有了新的代价，要么我们把j放在最后——就不能抵消了。不管是哪一种，代价都等于u。如果u=1那么代价为0。
习题9-14 uva1543
圆内接多边形可以直接当作若干三角形的叠加（角度跨过\(\pi\)的面积为负）。首先枚举起点i，再设f[j][k]表示前i个点选择k个构成的所有三角形面积之和最大值，最后算答案的时候把最后一个三角形加上去即可。注意初始条件应该是-INF而不是0（因为状态转移过程中的面积可能为负）。
习题9-15 uva12589
首先设各向量按\((x_i,y_i)\)依次排列，则总面积大小的两倍等于\(\sum_{1\le m \le k}{x_iy_i}+2\sum_{1\le j < i \le k}{x_iy_j}\)。
其次，从n=2的情形可以观察出一个事实：最优答案一定满足\(i< j,\frac{y_i}{x_i} > \frac{y_j}{x_j}\)，且\(\frac{y_i}{x_i}\)相同的元素的顺序可以任意。这是因为如果存在\(\frac{y_i}{x_i} \le \frac{y_{i+1}}{x_{i+1}}\)，那么交换\(i,i+1\)，总面积增大\(x_iy_{i+1}-x_{i+1}y_i \ge 0\)。
于是我们按照\(\frac{y_i}{x_i}\)从大到小排序，设f[i][j][y]表示在前i个向量中选j个，使得\(\sum{y_k}=y\)的最大面积，状态转移有选和不选两种。
★习题9-16 uva1634
考虑某个多边形，它一定存在y最小、且在此基础上x最小的点。枚举这个点（设为p0），把剩余满足要求的点按极角排序，则要选择的多边形可以按照逆时针分成一个个三角形。设f[i][j]表示从y轴开始选择若干三角形，使得最后一个三角形由p0,i,j组成，这样的面积最大值。这时存在一个问题：第一个三角形的下侧边可以有点，最后一个三角形的上侧边可以有点，而中间三角形的两侧都不可以有其他点。为此我们特殊处理：如果p0,i,j的三角形上侧和内部无点则可以进行初始化；如果两侧和内部无点则可以按照已有的状态进行状态转移，如果下侧和内部无点则可以用来更新答案。
实际写起来的时候代码略乱，而且漏了一个特殊情形：如果只有一个三角形，那么两侧都可以有其他点。
●习题9-17 uva10271
不难看出所有的A,B一定是相邻的。但是因为C可以任意选，所以一直找不到合适的dp算法。
搜了题解，发现正确的做法是反过来从大到小取，那么只要看前面的所有筷子取掉已经取的j-1套筷子和现在取的A,B2只以外还有没有剩的，只要有那就一定可以取为C。感觉这个想法很巧妙……但是自己想不出来。
习题9-18 uva1379
如果直接记录前4天的投手当然会超时，但是我们会发现每天比赛只有前5的选手才需要考虑（否则我们总能找到前5中空闲的一位，换成更优的）。于是预先按照胜率排序（如果胜率相同则无所谓），dp时只需考虑5^4种可能的状态转移，时间复杂度\(O(g\times 5^5)\)。
这题有个奇怪的坑，它的n,m范围可能超出了题面的范围，总是RE，把数组开大点就过了。
●习题9-19 uva1443
不难想到二分每个半段的重量和上限maxw，经过预处理后可以\(O(1)\)判断一个半段能不能取。
问题在于此时如何判断能否恰好组成m-1段：我先是设f[i]表示前i个细绳能组成最少多少段，然后判断是否有f[n]<=m-1。但是这是错的，因为可行的段数不是递增的——可以组成a段不意味着一定可以组成a+1段。然后后一直卡住了……想了几个\(O(nmd\log_2w)\)的算法，全部TLE。
于是又去搜题解了……原来可行的段数并不是没有递增性的！如果可以组成a段，那么它一定可以组成a+2段(在数量足够的前提下)——如果有>=6的段就直接把最中间的2(6,10...)/4(8,12...)个细绳拿出来作为新的一段；否则一定有2个>=4的段，把这两个各自从中间劈开即可。
所以有了递增性就有了最优子结构，设f[i][j]表示前i个细绳组成奇数(j=1)或偶数(j=0)段，最少组成多少段。判断f[n][(m-1)%2]<=m-1即为能否恰好组成m-1段。时间复杂度是\(O(nd\log_2w)\)的。
此外可以预先排除组不成段(n为奇数)和数量不够(n<2*(m-1))的情况，这就是所有无解的情况。
习题9-20 uva12222
设f[i][j][k]表示前i辆A方向的车、前j辆B方向的车，最后一次是A方向(k=0)或B方向(k=1)所需要的最小时间。枚举另一个方向行驶多少辆车子，这里有3个约束条件：起始时间、行驶时间和保持10s的距离。我们维护这一次行驶中，上一辆车的起始时间p和到达时间q，则第3个约束要求p'>=p+10,q'>=q+10，第1个约束要求p'>=t，第2个约束要求q'-p'>=d，满足这些条件即可进行状态转移。
一开始把题目条件看错了，认为同一方向的第二辆车子可以等第一辆走完，路空了再过去，但是其实是不可以的，所以需要第3维的状态。
习题9-21 uva1371
首先不难想出求两个串s1,s2编辑距离的dp转移方程：如果s1[i]=s2[j]则g[i][j]=g[i-1][j-1]，否则g[i][j]=min{g[i-1][j-1],g[i][j-1],g[i-1][j]}+1。对于这一题，我首先考虑的是设f[i]表示s1[1..i]的最小近似周期，那么f[i]=min{max{f[i-j],g[j][m]}}其中g[x][y]是s1[i-j..i-j+x-1]与s2[1..y]的编辑距离，dp转移类似先前。利用“刷表法”可以达到\(O(2nm^2)\)的时间复杂度（因为j至多枚举到2m——编辑距离不应该超过m。）
这个算法居然超时了，估计是数据组数不少，然而数据组数的范围却没给……注意到最大值的最小值这一特点，我们考虑二分k。这时需要注意到s1的分段情况是完全可以忽略的这一特点，我们把g[i][j]直接扩展到1<=i<=n,1<=j<=m，只不过加上一个特别的状态转移——如果g[i][m]<=k，那么下一段的匹配可以重新开始，令g[i][0]=0。这样的时间复杂度是\(O(nm\log_2m)\)的，跑了350ms。
★习题9-22 uva1579
首先预处理出每个区间能否套成一个组（区间内元素互不相同）以及能否作为最终的套娃（恰好是从1开始连续的数字）。设g[i][j]表示把i~j套成一个所需最小代价，枚举先套i~k,k+1~j再把它们合并。合并的代价这里比较麻烦：设x,y为将i~j从小到大排序，i~k和k+1~j的最小元素的排名，则合并代价为(j-i+1)-abs(x-y)。（因为只有abs(x-y)个套娃不用打开）利用二分查找可以在\(O(\log_2n)\)的时间内找到排名，总的时间复杂度是\(O(n^3\log_2n)\)的。
习题9-23 uva1322
利用sorter求最大值的过程可以视作是将1依次提升至n的过程——如果最大值在1，那么必须并且也只需要一条链，使得1每次从链上的某个sorter传递到右端点，最后到n的位置。不难看出求1~n的最大值只需要有这样一条把1传递上去的链就行了（因为其他的位置同样可以沿这条链传递）。设f[i]表示（利用目前的sorter）将1提升至i所需最小的链长度，不难看出f[i]是单调递增的。所以对于新的sorter\((a,b)\)，状态转移只需要更新\(f[i]=\min\{f[i],f[a]+1\}(a\le i\le b)\)。
因为每次更新的是一个区间，所以我们要利用线段树来优化这个dp过程。我的做法是每次先定位到线段树上的某几条被更新的线段上，然后对每条线段查询其中点的值，如果<=x那么直接给右儿子打上=x的tag并更新左儿子，如果>x那么不处理左儿子只更新右儿子。因为更新的时候还进行了查询，所以总的时间复杂度是\(O(m(\log_2n)^2)\)的。看网上的题解似乎可以直接更新不用查询中点？不是很能理解。