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总结之经典模型_学科竞赛_高中教育_教育专区。NOIP的dp模型总结 长郡 范进 DP 经典模型(母题总结) content L_S 免费馅饼 矩阵 dp 双塔 DP 石子合并 ...


NOIP的DP总结之DP类型

NOIP的DP总结之经典模型 暂无评价 14页 1下载券 NOIP中的DP基本类型 6页 免费...长郡 范进 Dp 类型总结 Content 资源型 dp 01 背包 完全背包 多重背包 二维...


noip算法总结2016

算法总结一、 动态规划和递推 dp 一般的解题步骤: 分析问题, 弄清题意——从原问题中抽象出模型——根据模型设计状态, 要求状态满足 最优子结构和无后效性—...


NOIP中的DP基本类型

NOIP的 DP 基本类型 1、背包模型 包括 0-1 背包、无限背包、有限背包、有价值背包、小数背包(贪心即可)等,是极为经典的模型,其 转化与优化也是很重要的。...


NOIP范围内的DP算法

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


noip2010模拟赛dp题选

NOIP2010模拟赛2 5页 免费 冲刺NOIP2010第三次模拟... 3页 1下载券 NOIP2010...小学五年级英语教学工作总结 大学教师个人工作总结 小学英语教学教研工作总结©...


Noip 2013 解题报告与参赛总结(PASCAL版)

Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013...例如 D2T2,明显有 O(N)的解法, 但却因想出了 NLogN 的 DP 而冲昏了头脑...


NOIP算法总结

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


算法总结

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


动态规划的很经典的教程

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

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