Climber.pI的OI之路

Dp札记

记录写过的dp题目，并分类，尝试总结出某类题目的一般模型.

(题目前打*的未编程验证)

【线性模型】

Tyvj 1049 最长不下降子序列问题 [O(n^2) [还存在基于二分查找的O(nlogn)算法]]

• [状态] f[i]表示从1到i的最长不下降子序列. 最大值需更新.
• [方程] if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)

NOIp 2004 合唱队形 [O(n^2), 双向最长上升子序列]

• [方程] f[i] = max{f[j]}+1 , 枚举k(0<=k<=n).

Rqnoj 164 最长公共子串 [记录方案 子串连续 O(n^2)]

• [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
• [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j],a[i-1]=b[j-1])|max{f[i-1][j],f[i][j-1]}

UVa 111/10405  [最长公共子序列问题,O(n^2). 可以使用滚动数组降至O(n).]

• [状态] f[i][j]表示 子串A第i个字符 和 子串B第j个字符 前 公共子序列长度
• [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j])|max{f[i-1][j],f[i][j-1]}

UVa 507 [最大连续和,O(n).]

• [状态] f[i]表示当前子序列和(非负)
• [方程] f[i]=max{f[i-1]+a[i], a[i]},递推过程中需更新最大值.

【矩阵模型】

*UVa 10285 滑雪 [记忆化搜索,最长下降子序列二维版本]

• [状态] f[i][j]表示从(i,j)开始的最长下降子序列长度.
• [方程] f[i][j] = max{f[i-1][j], f[i][j-1], f[i+1][j], f[i][j+1]}+1(f[i][j]>f[i-1][j]..)

UVa 108

• 最大矩阵和，O(n^3)，方程不会. 最大连续和的二维版本.

NOIp 2000 方格取数 O(n^4)

• [状态] f[i][j][k][l]表示两人分别到(i,j)、(k,l)所取过的数的和.G[i][j]表示方格里的数.
• [方程] f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])

NOIp 2008 传纸条

(1) O(n^4)

• [状态] f[x1][y1][x2][y2] 表示从出发点分别到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示该格的数.
• [方程] f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重复)
• [一个重要优化] 显然有y2=x1+y1-x2(y2>0),因而时间复杂度可以降到O(n^3).Cena显示总用时从近4s降到近0.3s，效果明显.

*(2) O(n^3)

• [状态] f[p][x1][x2],p表示经过的格子数.
• [方程] f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重复)

USACO 5.3.4/3.3.4 [矩阵dp,O(n^2)]

• [状态] f[i][j]表示以(i,j)为右下角的正方形最大边长
• [方程] f[i][j] = min{f[i-1][j], f[i-1][j-1], f[i][j-1]}+1 (0<=i,j<n)
• [预处理] 若G[i][j]=1则f[i][j]=1.

【背包问题】

USACO 3.3.2

• [状态] f[a1][a2][a3][a4][a5]为买a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5时，所需的最少价格
• [方程] f[a1][a2][a3][a4][a5] = min{f[a1-p[i][1][a2-p[i][2][a3-p[i][3][a4-p[i][4]][a5-p[i][5]+p[i][0]} (0<i<=s, ak-p[i][k]>=0,p[i][0]是优惠后的价格)
• [边界条件] f[0][0][0][0][0]=0;
• USACO官方解法很有启发性，用最短路，把每种状态[a1][a2][a3][a4][a5]（a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5）看成一个点，则至多7776个点，而每个优惠就是一条边，则至多105条边。 接下来就是求[0,0,0,0,0]到目标状态的最短路，用Dijkstra(Heap优化)即可.

USACO 3.1.2 [完全背包问题, O(n)或O(n^2).]

• [状态] f[i][j]表示放入第i个物体后剩余体积为j
• [方程] f[i][j] = f[i-1][j] + f[i][j-c[i]]+w[i]

USACO 3.1.6 [完全背包问题,O(n).]

• [状态] f[i]表示凑成i分邮资的最少邮票数.
• [方程] f[i] = min{f[i-v[j]]+1} (i-v[j] >= 0, 0<=i<n, f[0] = 0).

USACO 2.3.4

• [状态] f[i,j]表示前i种货币构成j的方法数，用c[i]记录货币的面值.
• [方程] f[i,j]=f[i-1,j]; 不用第i种货币
               f[i,j]=f[i-1,j]+f[i,j-c[i]] 用第i种货币，j>=c[i]

【树形】

USACO 2.3.2

• [状态] f[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：
• [方程] f[i,j]=∑(f[k,j-1]×f[i-1-k,j-1])(k∈{1..i-2}) 
• [边界] f[1,i]=1
• 我们要求的是深度恰好为K的方法数S，易知S=f[n,k]-f[n,k-1]。但需要注意的是，如果每次都取模，最后可能会有f[n,k]<f[n,k-1],所以可以用S=(f[n,k]-f[n,k-1]+v) mod v

【其他类型】

USACO 1.5.1 [数字三角形]

• [状态] f[i][j]表示从(i,j)开始经过的数字的最大和
• [方程] f[i][j] = max{f[i+1][j], f[i+1][j+1]}+a[i][j]

USACO 3.3.5 [博弈问题]

• [状态] s[i][j]表示从i加到j的和, 枚举l=j-i. f[i][j]表示从i到j先取者能得到的最大数字和.
• [方程] f[i][j] = s[i][j] - min{f[i+1][j], f[i][j-1]}

USACO 3.2.2

• [状态] f[n][m]表示至多m个1的n位二进制数数量
• [方程] f[n][m] = f[n-1][m] + f[n-1][m-1] (f[0][m] = 1)

posted on 2010-10-03 12:23 Climber.pI 阅读(456) 评论(1)  编辑 收藏 引用 所属分类: 动态规划