7.26
最长公共子序列lcs, O(N^2)
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0
7.27
编辑距离edit, O(N^2)
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + !(A_i==A_j))
初始化f[i][0] = f[0][i] = i
*参考[这里]http://en.wikipedia.org/wiki/Levenshtein_distance
*状态转移过程中, 充分不一定最优, 必要才是最优; 事实上边界条件总有其具体意义
*[相关]http://www.matrix67.com/blog/archives/333
最短回文串palindrome[poj 1159], O(N^2)
1.套用lcs, O(N^2), 60
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0, n - f[n][n]即为答案
*利用滚动数组优化, 空间复杂度O(N), 80
*关键语句k = 1 - k, 注意在内层循环外
2.套用edit, O(N^2), 30
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + 2*!(A_i==A_j))、
初始化f[i][0] = f[0][i] = i, f[n][n]/2即为答案
3.O(N^2), 30
f[i,j]表示将Ai..Aj变为回文串的最小代价，则
f[i][j] = f[i+1][j-1] (若Ai=Aj)
min(f[i+1][j],f[i][j-1])+1 （若Ai<>Aj）
4.利用位运算优化
http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html
硬币找零coin[完全背包], O(N^2)
f[j] = min(f[j], f[j-c[i]]+1)
初始化f[0] = 0, f[1..T] = INT_MAX
*注意下标非零 和 INT_MAX的溢出
7.28
导弹拦截missile[LIS + 二分], O(NlogN)
(1)二分查找O(logn)
f[i] = max(f[j] + 1) (j < i)
d[i] = min(f[k]) (f[k] == i)
易知d[i]单调, 因而可以利用二分查找降低复杂度, i最大值即LIS长度为t, 那么
i) f[i-1] < k <= f[i] (1 <= i <= t)
ii) 若k > 任意f[], 则f[t+1] = k;
iii) 若!k, 则f[1] = k;
*例子参见[这里]http://www.matrix67.com/blog/archives/112
[代码实现]
//情况ii和iii需要单独处理
x = 1; y = t;
while (x <= y){
m = (x + y)/2;
if (f[m-1] < k && k <= f[m]) break;//对于最长上升子序列和最长不下降子序列判定条件不明???
//if (f[m-1] < k && k <= f[m]) return m;
else if (k > f[m]) x = m + 1；
else y = m - 1;
//return x;
}
*利用注释, 可以避免对情况ii的单独处理LIS的方案, 记录方案需要使用pre数组, 范例不知???
*需要注意的是, f数组给出的并非是一个
(2)最少链划分 = 最长反链长度(关于偏序集, 参见《组合数学》P73)
[Dilworth定理]令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
最长不下降子序列lis[LIS + 二分], O(NlogN)
对[1..k-1][k+1..n]两个序列分别进行一次LIS即可.
*问题的关键之处在于第一次理解不彻底和浮躁, 以及对于困难程度的不合理估计.
7.29
加分二叉树tree[区间 + 记录方案], O(N^3), 20min
f[i][j] = max(f[i][k-1] * f[k+1][j] + A[k]) (i <= k <= j)
初始化f[i][i] = A[i], f[i+1][i] = 1
[记录方案]pa[i][j] = k, 递归即可, [边界]pa[i][j] == i 或者 j, 以及i == j的情况
整数划分separate[区间 + 记录方案], O(N^3), 2h
f[k][i]表示序列1..i分成k段的最大值
f[k][i] = max(f[k-1][j-1] * A[j][i])
pa[k][i] = j
初始化f[1][_] = A[1][_], 其他f[][] = -1
*注意等号情况同样需要更新
if (f[K][i] <= f[K-1][k-1] * A[k][i])
f[K][i] = f[K-1][k-1] * A[k][i],
pa[K][i] = k; //记录方案
*将[pa[k][i], i]加入答案, 递归[1, pa[k][i]-1], [边界] k == 0
*在Win下使用long long占位符为"%I64d", 在Linux下占位符为"%lld", 考试中利用<fstream>避开占位符问题
凸多边形的三角剖分division[区间]
f[i][j] = max{f[i][k] + f[k][j] + w(i, j, k)} (i < k < j)
初始化1<=i-j<=2的f只为0, 其他为-1
*表达式中同时出现long long和int的话, 会自动转换为int
*只过了6个点, 原因不知 -> 数据错误, 最后4个点output一样
*各种神牛们普遍指出没有考虑i>j的情况 -> 怎么写???
机器分配machine[区间], O(N^3)
f[i][j] = max(f[i-1][k] + A[i][j-k]) (0 <= k <= j)
初始化f[][] = 0, f[i][j] = max(f[i][j], A[i][j])
*注意读题"第i个公司分配j台机器的盈利", 不是分配第j台机器的盈利
装箱问题box[分组背包], O(N^2), 30min
f[i][j] = max{f[i-1][j], f[i-1][j-c[i][k]] + w[i][k]}
初始化f[][] = 0
*读题时注意变量的对应关系
*注意本题中背包不一定要装满
7.31
最长前缀prefix[判断性dp], O(kN), 70min
f[i] |= f[i - len[j]] & check(i - len[j] + 1, j) (1 <= i,j <= n)
初始化f[] = 0, check(x,y)表示主串[x,x+len[y]-1]和前缀y是否相同
*弄错j和len[j], 注意方程的字母指代, 以及实现中的字符指针位置, 注意静态查错[30min]
*[8.4优化]把check函数直接写在循环中, 如果f[i] == 1直接break -> 依旧超时三个点
*[8.5优化]i的上限为min(n, ans + 20), 更新f[i]的时候记录ans即可 -> AC
8.1
关键子工程project[DAG最长路], 70min
f[i] = max(f[j] + w[i]) (G[j][i] == 1)
初始化f[i] = w[i]
记录方案, 利用f[i] == w[i] + f[j] (G[j][i] == 1)
*利用定义求拓扑排序, 输出方案可以利用队列将递归转化为迭代, 无解情况用flag标记(inq数组表示是否在队列中)
*在纸上写出关键部分的代码, 两倍行距(比如递推或者记忆化函数, 输出方案的函数)
8.2
三角蛋糕trigon[坐标dp], 130min
[做法1](需保留空格)
f_[i][j]表示以(i, j)为顶点的Rt△的最大边长
对于倒三角形, 自右向左 f1[i][j] = min(f1[i+1][j], f1[i][j+1]) + 1
自左向右 f2[i][j] = min(f2[i+1][j], f2[i][j-1]) + 1
对于正三角形, 自右向左 f1[i][j] = min(f1[i-1][j], f1[i][j+1]) + 1
自左向右 f2[i][j] = min(f2[i-1][j], f2[i][j-1]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f1[i][j], f2[i][j])^2的最大值即为答案
[做法2](不需保留空格)
f[i][j]表示以(i, j)为顶点的△的最大高度
对于倒三角形, f[i][j] = min(f[i-1][j], f[i-1][j+1], f[i-1][j+2]) + 1
对于正三角形, f[i][j] = min(f[i+1][j], f[i+1][j-1], f[i+1][j-2]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f[i][j])^2即为答案
*输入需保留空格, 卡了30min(排除ASCII为10或13的字符即可)
*没有考虑正方向, 大约2h时对照std发现
*有两个点数据错误, 对照std后发现std仅当横坐标为奇数是考虑倒三角形, 横坐标为偶数时考虑正三角形, 而题目中无此限制
*学习利用批处理对拍的写法
@echo off
:again
gen
trigon
trigon_me
fc trigon.out trigon_me.out > nul
if not errorlevel 1 goto again
选课course[树形dp]
[做法1]多叉转二叉
f[i][j]表示以i为根节点的树中, 选择j门课
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
*无法记录方案 -> gXX表示比较困难
[做法2]泛化物品
??? -> 想撞墙 -> 需要学习
通向自由的钥匙key[树形dp], 150min, zoj 2280
f[i][j]表示以i为根节点的数, 花费能量为j时可以拿到的最多的钥匙数
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-i.c] + i.v) (o<=k<=j-i.c)
初始化f[][] = -1, 边界处理f[i][j] = 0(i<=0 || j<0)
*记录各点邻接矩阵, 利用dfs构造树(注意处理后取消邻接), 并多叉转二叉 -> 30min
*对于f[i.r][j]不必在记忆化搜索函数中遍历所有兄弟, 只遍历最近的即可
*注意读题, 出发点为1, i.c和i.v非负 -> 1.5min
*注意静态查错, 如记忆化搜索中dp(i, j)打成f(i, j)的情况
*觉得比较晕的时候等一下再调题, 可以先干点别的, 这样可以减少时间的浪费
警卫安排security[树形dp], 100min
[状态]
f[i][0]表示以i为根节点, 并在i安排警卫的最小花费
f[i][1]表示以i为根节点, i的父节点已安排警卫的最小花费
f[i][2]表示以i为根节点, i的子节点已安排警卫的最小花费
[方程]
f[i][0] = Σmin(f[i.son][0], f[i.son][1], f[i.son][2]) + i.v
f[i][1] = Σmin{f[i.som][0], f[i.son][2]} (i不是树的根节点)
f[i][2] = min{Σmin{f[i.son][0], f[i.son][2]}(i.son != k) + f[k = i.son][0]}
[初始化]
对于叶节点, f[i][0] = i.v, f[i][1] = 0, f[i][2] = i.v
对于其他值, f[][] = -1
*对于根节点的寻找, 利用prev[i]记录i的前驱, 若!prev[i], 则i为树根
*结合批处理和makedata以及小范围暴力程序, 可以有效地避免各种错误及极端情况 -> 需要学习搜索
*对于这类题目, 思考的关键在于分类写出方程, 并注意方程的边界条件(类似:tyvj 没有上司的舞会)
*对于树形dp, 存在两种类型; 一种是对于加权路径长度限制, 另一种则是求加权最值
8.4
青蛙的烦恼frog[区间dp]
初看是最小生成树问题, 但是此题有几个特别的性质:
1.以1号荷叶为起点, 终点不定
2.遍历荷叶的最短路径是一条链
3.题目给出的坐标顺序是一个顺时针方向的多边形
4.最短路径不相交(画一个四边形, 利用三角形性质可以观察到)
根据性质1和2, 容易得出O(N^3)的方程, 很明显会超时
f[i][j] = min(f[k][j-1] + d[i][k]) (i!=k)
-f[i][j]表示以i为起点, 长度为j的最短路径, 初始化f[i][1] = 0
进而考虑性质3和4, 因而对于点1, 只能选择相邻的点2和n, 可以得到O(N^2)的方程
f[i][j][0] = min{f[i+1][j-1][0] + d[i][i+1], f[i+1][j-1][1] + d[i][i+j-1]}
f[i][j][1] = min{f[i][j-1][1] + d[i+j-1][i+j-2], f[i][j-1][1] + d[i+j-1][i]}
-f[i][j][0]表示以i为起点, 长度为j的最短路径, f[i][j][1]表示以i为终点, 长度为j的最短路径, 初始化f[][1][] = 0
-一个实现上的小优化, 保证d[i][j](i<j)
*注意静态查错, 区别变量名, 思考算法的过程应该长于调试的过程
*修正了测试点6
火车进站train[线性dp], 70min
1.M <= 3 -> 可以分类讨论
2.只存在一条轨道, M只能决定轨道的长度 -> 如果同时在轨道中, i在j前的必要条件是i.s<=j.s和i.t<=j.t
3.小站工作人员可以任意安排这些火车进站的先后排列 -> 记忆化搜索
4.小站允许几辆火车同时进站或出站 -> 所有条件都可取等号
M = 1, f[i] = max(f[j] + 1) (i.t <= j.s)
M = 2, f[i][j] = max(f[j][k] + 1) (i.t <= k.s)
M = 3, f[i][j][k] = max(f[j][k][l] + 1) (i.t <= l.s)
初始化f = 0, 利用vis记录是否计算过, 各下标互不相等
*枚举过程中注意剪枝, 利用i!=j和i.s<=j.s,i.t<=j.t逐层处理即可
*[读题]明确要求的是什么, 存在哪些条件, 写list
*[未验证]先对以进站时间为第一关键字, 出站时间为第二关键字进行快排, 然后直接递推, 下标满足i < j < k < l
快餐问题meal[资源分配(不妨认为是背包)dp + 贪心优化] -> 类似, usaco 3.4.4 rocker
f[k][i][j]表示k条生产线生产i个汉堡, j个薯条时生产饮料的最大值, p[k][i][j]表示第k条生产线, 其他同.
f[k][i][j] = max{f[k][i-ki][j-kj] + p[k][i][j]}
sum[i] = sum[i-1] + A[i]
初始化f[1][i][j] = p[1][i][j], f[2..n][i][j] = -1, 复杂度O(N*100^4)
几个优化
1.注意到每种物品总数小于100, 最大产量的上限是lim = min(100/a, 100/b, 100/c, sum[n]/(a*p1+b*p2+c*p3))
2.为了避免数组越界, i的上限是min(lim*a, sum[n]/p1), j的上限min(lim*b, (A[k] - i*p1)/p2);
ki的上限min(i, A[k]/p1), kj的上限min(j, (A[k] - ki*p1)/p2) -> 对于逗号右边, 其实就是ki*p1+kj*p2<=A[k]
3.将程序中的min/max用if语句替代
4.对于每一套生产线, 尽量成套生产
[反例]
1 1 1
2 3 7
3
15 16 17
贪心可得最大值为3, 实际上15 = 7 + 3 + 3 + 2, 16 = 7 + 3 + 2 + 2 + 2, 17 = 7 + 7 + 3, 最大值为4;
利用优化1和2可以过5个测试点, 优化3可以进一步优化时间常数, 利用优化4可以过9个测试点
AC程序参见[此文]http://hi.baidu.com/zijingningmeng/blog/item/2761617e2afe7ae32e73b3b3.html
*调试过程中的主要问题是边界溢出(没有区分是否计算过), 变量名写错
*网上有说法表示去掉每种物品的件数限制后, 题目变成网络流 -> gXX证伪
*比赛的话, 不妨小数据(n<5)DP, 大数据(n>=5)贪心, 这样应该可以得到超过一半的分数
卡车更新问题truck, O(N^2), 1h
f[i][k]表示第i年某车已使用了k年
f[i][k] = max{f(i+1, 1) + R[0] - U[0] - C[k], f(i+1, k+1) + R[k] - U[k]}
初始化f[][] = -1, 边界条件f[i][k] = 0(i>N,k>K), 利用记忆化搜索实现
记录方案利用bool型数组prev[i][j][k]记录是否购买新车, 递归即可
*尽可能不换新车
*利用样例构造树, 写出状态即可得到方程
*测试点1存在等价方案, 已修正数据(可能需要Special Judge)
*f[i][j][k]中i和k可以唯一确定状态, 因而可以去掉中间1维
选课course[树形dp + 记录方案], 多叉转二叉实现
f[i][j]表示以i为根节点的树中, 选择j门课
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
[记录方案]
利用print(i, j)递归, vis[i][j]表示是否已遍历, [边界]i∈[1, m], j∈[1, n]
right[i][j]表示f[i][j]是否等于f[i.r][j]
prev[i][j] = k表示f[i][j]由f[i.l][k],f[i.r][j-k-1]推得, 这时需记录p[i] = 1
从1到n判断p[i]直接输出即可.
8.5
广场铺砖问题floor[状压dp], 2h
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即为答案
对于每个f[i-1][S']利用dfs(当前行i, 当前行状态s1, 下一行状态s2, 当前行指针k)寻找S
if(!(s2 & 1<<k) && !(s2 & 1<<(k+1)))
dp(i, s1, s2, k + 2);//存在连续两个空位, 即横放
dp(i, s1, s2 ^ (1<<(k)), k + 1);//对当前位取反, 即竖放
利用int保存每一位的摆放方式, 1表示当前行被上一行占用, 0表示当前行未被占用
[边界]k = 0, 递归过程中k > w则退出
硬木地板floor2[状压dp]
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即为答案
*实现无能, 最终放弃 -> 我应该去学位运算优化BFS -_-
*鱼牛《状态压缩》理解不能, NOI导刊朱全民文章code不全.
*耗时最长的题目往往不是表面上的难题, 而是那些被简单估计的难题