tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP的DP总结之经典模型


长郡 范进

DP 经典模型(母题总结)
content
L_S 免费馅饼 矩阵 dp 双塔 DP 石子合并 选课 数字三角形 打砖块 子矩阵 最大子段和 方格取数 Hanoi 数的划分 逆序对 最短回文串 硬币问题 形成非降序列的最少合并次数

L_S 问题 LIS &LCS& LCIS

r /> 长郡 范进

话说 LCS 有 O(n*m)的算法,LIS 也有 O(n*m)的算法; XX 日,LIS 被栈和二分优化了,复杂度变为了 nlogn, q[1]:=a[1]; top:=1; for i:=2 to n do begin if a[i]>q[top] then begin inc(top); q[top]:=a[i]; end else begin l:=1;r:=top; while l<r do begin mid:=(l+r)div 2; if q[mid]>a[i] then r:=mid else l:=mid+1; end; q[l]:=a[i]; end; end; 于是 n 排列的 LCS 也被优化了,也达到了 nlogn.

长郡 范进

nlogn 的 LCS:设有序列 A,B。记序列 A 中各个元素在 B 中的位置,用序列 C 存,求 C 的 LIS 即可。 LCS 与 LIS 结合,于是有了 LCIS,LCIS 有 n*m 的算法。 代码如下: for i:=1 to n do begin t:=0; for j:=1 to n do begin if a[i]>b[j] then if f[j]>t thent:=f[j]; if a[i]=b[j] then if t+1>f[j] thenf[j]:=t+1; if f[j]>ans then ans:=f[j]; end; end;

解释可以参考资料里的某文档或百度文库。

变式训练:导弹拦截,合唱队型,船,交错匹配,最高线段 覆盖,

最大子段和 *1*一般的最大子段和:

长郡 范进

F[i]:=max{f[i-1]+a[i],a[i]} Ans:=max{f[i]} *2*元素不可重复计算的最大子段和(cwx 吃面包) : S[a]表示 a 到 b 不重复计算的子段和, F[a]表示 s[a]出现过的最大值。 Pre[k]表示元素 k 上一次出现过的地方 For b:=1 to n do Begin For a:=pre[w[b]]+1 to b do Begin S[a]:=s[a]+w[b]; F[a]:=max(f[a],s[a]); End; End; Ans:=max{f[a]} *3*最大 M 子段和 F[i,j]表示前 i 个数,i 属于第 j 子段时的最大值。 G[I,j]表示前 i 个数,分了 j 个子段时的最大值。 F[I,j]:=max{f[i-1,j],g[i-1,j-1]}+a[i]; G[I,j]:=max{g[i-1,j],f[i,j]}. 空间可以优化。 反思:状态的巧妙设计,互补设计。

长郡 范进

M=2 时另有做法: 顺做一次最大子段和 x[i],到做一次最大子段和 y[i], Ans:=max{x[i]+y[i+1]}. 枚举断点法,很实用! *4*长度限制的最大子段和 可用单调队列优化。

最大子段和

最大 m 子段和(——必做! ) (n<=106 ,m<=50,允许空间 O(n)) 算法 1: F[i,j]表示前 i 个数,i 属于第 j 子段时的最大值。 F[i,j]:=max{f[i-1,j],f[k,j-1]}+a[i].(1<=k<i) 过不了! 算法 2: G[I,j]表示前 i 个数,分了 j 个子段时的最大值。 F[I,j]:=max{f[i-1,j],g[i-1,j-1]}+a[i]; G[I,j]:=max{g[i-1,j],f[i,j]}. 过不了! 算法 3: 根据分析 g(i,j)=max{g(i-1,j),f(i,j)}发现,g 要么和前一个

长郡 范进

状态 g(i-1,j)相同,要么和此时所得的数 f(i,j)相同。 同样的,f(i,j)=max{f(i-1,j)+a[i],g(i-1,j-1)+a[i]}中,f-a[i]要么和前 一个状态相同,要么和前一个最优解 g 相同。所以,我们可 以用一维数组来代替二维数组。 F[j]:=max{f[j],g[j-1]} +a[i]; G[j]:=max{f[j],g[j]}. 成功 AC!

最大不重复子段和:cwx 吃面包问题。 平方做法。

子矩阵问题 *1*最大 01 子矩阵 枚举下边界,利用悬线的观点,然后有两种做法:路径压缩法和两次 单调队列法。 其实还可以将不要的一方赋值为-oo, 从而转化为*3*最大子矩阵问题。
*2*另外,最大 01 子正方形:

f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f);

*3*最大子矩阵

长郡 范进

枚举上下边界,化二维为一维(最大子段和问题) 。 变式: *1*找一个矩阵,使得其中的 1 的个数减去 0 的个数最大,输出最大 值。 方法:将 0 变为-1,问题转化成最大子矩阵 *2*AHOI 2007 宝库通道 *3*最大面积 【题目描述】 已 知 一 个 大 矩 形 的 长 和 高 l 和 w(1<=l,w<=10000) , 有 n(n<=5000)个点在大矩形内部(包 含边上) ,求大矩形内部边平行 于这个大矩形且点都不在小矩形内的小矩形的最大面积 (点 在小矩 形边上不算在小矩形里面) 。 【输入输出】 输入文件第一行为整 数 l 和 w。 接下来一 行为整数 n。 接下来 n 行为这 n 个点的坐标整数 x,y(0<=x<=l,0<=y<=w)。 输出文件为一个整 数,即小矩形最大面积。 解析:点数较稀的问题,可以另辟蹊径。 分三种情况:某两端无限制,另两端限制;三端限制;四方限制。 可以先两遍 Qsort 再做。 *4*最大子立方体问题 枚举一组边 i 的起始,压缩进矩阵 B[I,j]+=a[x,I,j] 枚举另外一组边的起始,做最大子矩阵

长郡 范进

数字三角形 *1*朴素的数字三角形 f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);

*2*数字三角形 2 晴天小猪历险记之 Hill 同一阶段上暴力动态规划 if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]

*3*数字三角形 3 小胖办证 f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]) 以上*2**3*用到二次 dp。

三角蛋糕 剪围巾 方法:枚举分割线。 过河卒:求方案数的一般方法。

打砖块 朴素的打砖块 f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);

长郡 范进

数字三角形 6 优化的打砖块 f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}

打砖块(模型转化) *1*曲线转化(mlj) *2*旋转转化

这样就变成了从每一行的开头连续取数, 且第 i 层取的数字个数不能 超过第 i-1 层取的个数+1。这样就没有后效性了。 有子弹奖励的打砖块:难!应当不考?!

最短回文串

有两种做法: 1- F[I,j]表示将 s[I..j]变为回文串的最小代价, 方程如下: F[I,j]=f[i+1,j-1],s[i]=s[j] F[I,j]=min(f[i+1,j]+1,f[I,j-1]+1);s[i]<>s[j] F[i+1,j]+1 表示在 j 后插一个字符 F[I,j-1]+1 表示在 i 前插一个字符 2- 将原串 数组) (a 与原串的倒序 数组) (b 做一次 LCS,

长郡 范进

用原串长度减去 LCS 长度, 即为需要插入字符的个数。 证明:在 a 数组中加上 b 中与 a 不同的 n-LCS 个,在 b 数组 中加上 a 中与 b 不同的 n-LCS 个,得到 a 与 b 完全相同。 (自 己想想)

逆序对 *1*求逆序对个数:dp 或树状数组或归并。 *2*逆序对个数为 k 的排列数: 排列 dp:f[I,j]表示 i 排列中逆序个数为 j 的排列数,
f[i][j] =
j k=j?i f

i ? 1 [k]可以用前缀和优化

或者 f[i][j] = f[i][j-1]+f[i-1][j]-f[i-1][j-i-1]

排序工作量之新任务 F[I,j]表示前 i 个数构成的全排列中, 逆序对为 j 的方案数。 G[I,j]存储最佳方案。复杂度 O(n^5)

一些题

Poj

1088

1276(**) 1837

1062 1160 1185

长郡 范进

双塔 DP (类差值问题) Poj1837 balance , : NOI2011 嘉年华, LZN 的 team(分组) ,LDL 的 lines(排队) ,搭建双塔,任务 调度(难) 。

装箱问题 尽量均分的目标型 DP: 先求 half, 转化为求容量为 half 的装箱问题。 题目:挤牛奶,石子归并,补圣衣

滑雪 *1*原版:水 *2*上下走(weakness) :转化为找两起点相同的单增的路。 先离散化,F[p,q]表示一条路到达高度为 p,另一条路到达高度为 q 时的最长路经和。

形成非降序列的最少合并次数
给定一个序列,你每次可以合并相邻两个元素,新的元素为这两个元 素的和。你需要使得若干次合并之后的序列非降,求最小合并次数。 [LYP 的并,tyvj2008tower,QW 的 CCL]

解析:设 f[i]表示以 i 结尾的所有数分成的组数,g[i]存第 i 个数结尾的 数它这组的数的值,那么转移为: f[i]=max{f[j]+1}(j<i,s[i]-s[j]>=g[j]),转移 f[i]的同时转移 g[i]为 s[i]-s[j],

长郡 范进

初始 f[i]=1,g[i]=s[i]. 通过观察我们发现,设当前分了 k 组,第 i 个数,最坏分到第 k 组,所以,f 数组一定是不减的,所以 j 只要倒着循环,找到第一个满足 s[i]-s[j]>=g[j] 的 j,转移 f[i]. 开始认为此方程有问题 {存在 p, 使得 f[p]在所有已得到的 f 值中最大; 若存在 q 满足 f[q]<f[p]且 q>p,则此方程有 bug。但是这种情况不存 在!f 值单调非降!}, 另外有单调队列做法。

归纳总结: 类型 1:消值求积分。 (断点型) A. 最少矩阵乘法次数 B. 凸多边形的三角形划分 C. 删字游戏 D. 能量项链 E. 石子合并 这类问题的通用方程为: F[I,j]=max(or min){f[I,k]+f[k,j]+c[i]#c[k]#c[j]} 运算符#由题意决定 实现有三种:记忆化、倒推、按长度推。 类型 2:数字串中添加加号(乘号) ,求最值。 A. 最大乘积

长郡 范进

B. 最佳加法表达式 C. 统计单词个数 D. 数字游戏 这类问题的通用方程为: F[I,j,k]=max(or min){c[I,s]#f[s+1,j,k-1]} 运算符#由题意决定 另一种写法:F[I,k]=max(or min){f[j,k-1]#c[j+1,i]} 以上两种类型都有递归方程, 可以递归解, 也可以转非递归。 类型 3:尽量均分问题(装箱问题) 。 题 33……37,40。 方法:先求 half,转化为求 V=half 的装箱问题。 类型 4:类差值问题(也称目标型 dp) 。 这类问题,状态要记录一个差值。长短互转的忘了是哪个 题了。 。 A. 多米诺骨牌 B. 取模方案数 C. Poj1837 balance D. 搭建双塔 E. Process the Tasks zoj 3331,10 年浙江省赛) ( (难) AC) ( 这题方法:http://blog.csdn.net/petercsj/article/details/5626679
dp[i][j][x]表示当前处理完第 i 件任务后,两台机器的结束时间差为 j 时,最早 的总结束时间。x 表示 j 的正负. 同样,这题也有 3 种转移: 1:第 N 项工作加在较高的塔上,此时虽然高度差增加,但由于 N+1 项工作必

长郡 范进

须在第 N 项开始之后才能开始,因此在另一塔的高度也增加了空闲值。 exp:A:20 B:10 将第 N 项发任务放在 A 上后,A->30,而 B 中 10-20 那段时间变为不可用, 因为题目条件 3。因此 B 的高度变到 20。也正因为如此,时间差 最多只到单件任务时间的最大值。 2:第 N 项工作加在较低的塔上,使高度差减小,但原先的高塔仍然较高 3:第 N 项工作加在较低的塔上,使低塔高度超过高塔 最后 dp[N][0-max][0|1]中的最小值即为答案。


推荐相关:

NOIP范围内的DP算法

NOIP范围内的DP算法_IT/计算机_专业资料。浅析 NOIP 范围内的 DP 算法刘伟潜 ...2.一些经典的 DP 模型一道 DP 往往可以通过多种方式去做,所以以下分类并不...


算法总结

算法总结_IT/计算机_专业资料。NOIP算法总结 我大致...没有什么固定的知识点, 但还是有一些经典的模型应该...6、 关于混分: 超时的搜索/DP 往往能比错误 的...


算法归纳总结

其次还要关注状态表示中的隐藏含义, 例如 NOIP2011 ...策略一:建立最普通的网络流模型,超级源点连向 N ...[j]; } } Return 0; } 几个典型 DP 式: ...


Noip2013总结-顾霆枫

Noip2013 总结 By GTF 总览这次考试败得很惨,200 分。300 分的一等奖啊!差...以下是问题分析: 一、 算法算法方面的欠缺主要在图论和 DP 方面。 图论方面有...


NOIP算法总结

NOIP算法总结_电脑基础知识_IT/计算机_专业资料。...4. 线性 DP 22 ?线型动态规划问题,最典型的特征...树型动态规划 (1)概述:它的基本模型都是一棵树...


NOIP大牛训练计划

最长递增子串、三角剖分、记忆化 dp 6.博弈类算法...第三阶段是锻炼在比赛中可以快速建立模型、想新算法...NOIP算法分类总结(C语言... 13页 免费 信息学联赛...


动态规划的很经典的教程

DP 有些感想,就写了这个总结: 第一节 动态规划...来源:NOIP1996(提高组) 第四题 这样一改就是经典...2.6 其他问题还有一些题目虽和一写基本模型相似但...


4种常见的动态规划模型

这类型的题目应用挺广的 (noip1996 提高组第 4 ...1 2 3 分析:这是一道很典型的区间模型动态规划...模型,具体问题具 体分析的, 多归纳总结, 掌握 DP...


算法总结

算法总结_IT/计算机_专业资料。noip2010NO.1 數論 ...組合直接數了,寫起來有些麻煩,也許用 dp 更簡單些...带权中位数 NO.2 图论 总纲 NOIp图论算法与模型...


NOIp06-15题解分析

noip2007 题 1:快排统计输出,桶排会超的 题 2:字符串模拟 题 3:dp+高精度+压位 题 4:语文题, ,floy 求直径最小值 noip2006 题 1:经典区间 dp 题 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com