当前位置:首页 >> 学科竞赛 >>

信息学奥赛中的动态规划


主讲人:FireStorm

数字三角形
——IOI1994

? 题目描述 Description 如图所示的数字三角形,从顶部出发,在每一结点可以选择向左走或得向右走,一直 走到底层,要求找出一条路径,使路径上的值最大。
? 输入描述 Input Description 第一行是数塔层数N(1<=N<

=100)。 第二行起,按数塔图形,有一个或多个的整数,表示该层节点的值,共有N行。 ? 输出描述 Output Description 输出最大值。 ? 样例输入 Sample Input 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 ? 样例输出 Sample Output 86

解法1:暴搜
?

DFS一遍遍历整个数字三角形,对于每个节点,我们有2个选 择,那么,n层的数字三角形有2^n种可能,所以时间复杂度 为O(2^n)

T L E!

解法2:贪心
?

一路下去只找最大的可以吗?

WA!

解法3:最长路
? ? ?

将整个数字三角形看作一个由点和边组成的图,以a[1][1]为 起点,求它到a[n][i](1<=i<=n)的最长路 Dijkstra算法:本题部分数据有负值…… SPFA算法:O(kM)的话应该能行

?
?

Bellman-Ford算法:O(VE)有点危险啊
Floyd算法:O(n^3)你确定要用吗?

方法可行但是打起来好麻烦……

还有什么更好的算法吗?

当然有!那就是本课要讲的内容——动态规划

?

分析这个数字三角形,我们可以发现:一个节点只会受到上 面两个节点的值的影响,而上面节点的值也只会受到更加上 面的节点的值的影响……由此可写出递归式

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
?

上面这个递归式在动态规划中被叫做状态转移方程式,根据 这个式子,我们可以从dp[1][1]开始递推,直到数字三角形 的最后一行。 时间复杂度O(n^2),完全无压力~

?

? ? ? ? ?

动态规划是优美的 动态规划是神奇的 动态规划是有趣的 动态规划是简单的 动态规划是卡骗分的

?
? ?

动态规划是禁贪心的

什么鬼!!!

动态规划是防止爆0 的 动态规划最简单最好玩了

?

我最喜欢动态规划了!!!

0-1背包问题
——Merkel and Hellman 1978
——NOIP2005普及组

题目描述 Description 由于该题目的题目描述版本过多,不再描述 输入描述 Input Description 输入第一行有两个整数T(1<=T<=1000)和M(1<=M<=100),用一个空格隔 开,T代表最大重量,M代表物品的数目。接下来的M行每行包括两个在1到100之间 (包括1和100)的整数,分别表示采摘某个物品的时间和每个物品的价值。 输出描述 Output Description 输出包括一行,这一行只包含一个整数,表示在不超过规定重量的情况下,可以拿到 的最大价值。 样例输入 Sample Input 11 11 样例输出 Sample Output 1 数据范围及提示 Data Size & Hint 【数据规模】 对于30%的数据,M<=10; 对于全部的数据,M<=100。

?老规矩:
?暴搜TLE

?贪心一定WA
?最短路你可以试试……

怎么办?

动态规划才是王道!
? ?

我们先分析下暴搜的过程: 我们对每个物品进行了搜索,产生了大量的状态,每个状态包括三个要 点: 1.目前已用的背包的容量,这个不用多说 2.目前已经获得的价值,这个也不用多说 3.目前已经处理了多少物品,记录下已经处理物品数量的原因是由于每 个物品只能拿一个,所以要记录下已经处理了多少物品,防止以后重复 处理

? ? ?

有什么想法没?

为什么不记录下相同的状态时的最优策略呢?

?

在使用相同的容量和处理了相同的物品后,剩下的搜索过程应该是相 同的,假如共有n个物品,我们已经处理了m个,那么还需要处理的物 品数量就是n-m,但是在背包剩余体积为v的情况下,剩下n-m个物品 产生的最优解应该是相同的,这样就可以简化搜索过程,但是前面的 怎么办呢?前面的当然要最好的! 于是,我们得到一条结论: 在其他状态均相同的情况下,选择最好的总是对的!

?

?

所以,我们可以开始优化这个搜索了:每次搜索到一个状态,就从之 前搜到过的状态里找一遍,如果看见可以替换的状态就更新……

?

众:你不觉得更慢了么……

?

所以,怎么办呢?

? ? ?

你还记的桶排序吗?直接用数组下标记录,时间复杂度O(1) 这个可以这样做吗? 没问题!看数据范围:1<=T<=1000,1<=M<=100,状态只需要记 录下重量和已处理的物品数,空间复杂度O(TM),128MB内存没问 题 至于状态转移方程式的话: dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i])

?

?

我一般习惯写成:
dp[i+1][j]=max(dp[i][j],dp[i+1][j]) dp[i+1][j+v[i]]=max(dp[i+1][j+v[i]],dp[i][j]+c[i])

?
?

这个看个人喜好就可以了,没有强制要求的
处理时,只要for一遍,把数组填充好就可以啦,时间复杂度O(TM)

?

P.S.:这字母是谁规定的,这么恶心

如果卡你空间怎么办?

滚蛋动数组
? ? ? ?

你还记得斐波那契问题怎么做的吗? c=a+b a=b b=c 根本不用开一个数组嘛! 这个问题也一样,除了前一行,其他的状态根本就用不到嘛! 那么:

? ?

也就是说,数组只留2行就可以了,每处理完一行, 就把第二行的结果放回第一行,继续处理 滚动数组是用时间换空间的一种策略

有没有更好的方法呢?

? ? ?

背包问题可以用一维数组解决你造吗? 由于重量没有负数,所以可以直接向后转移,而且不用向下 转移了,但这样就有可能重复处理一个物品,怎么办? 很简单,改变下方向,从后往前处理就可以啦~

?

至此,01背包完满完成~

难度增加的背包问题
更加喜(sang)闻(xin)乐(bing)见(kuang)的背包问题

超大背包问题
?

每个物品只能拿一次,物品数量M<=100,背包容量T<=10^9, 每个物品的价值<=100,每个物品的重量<=10^9

?

由于本题物品的价值非常小,所以可以将dp数组改为由已处 理的物品数量和价值,数组内存储内容改为当前所需的重量 即可

二维背包问题
?

对于每个物品,分别有体积v和重量w,求体积和重量均不超 标的情况下可以拿到的最大价值

?

维数改为三维,改变下转移,也可简化为二维,从后往前for 得出正确答案

完全背包问题
?

每个物品可以拿无限次,只要不超过最大重量即可

思路1:背包+枚举
?

在状态转移时枚举每个物品可以拿的次数,时间复杂度 O(VNK)

优化1:减少物品种类
?

对于一个物品来说,假如它的重量大于等于另一个物品且它 的价值比另一个物品低,那么要它何用?可以直接省略掉该 物品,所以只要先预对所有物品进行一遍O(n^2)的预处理, 就能带来很大的优化

优化2:转化为0-1背包
?

将一个物品看成多个物品,时间复杂度没有发生变化
但是大家记得一个叫做鬼谷子的钱袋的题吗? 如一个物品最多可以拿10个,则可以拆分成:1个该物品,2 个该物品,3个该物品,4个该物品,达到log(k)的级别,也 是个不错的优化

?

?

思路2:用一维背包解决
?

大家还记得一维的背包解决方案吗?此题也可,只不过为了使一个物品可以重复 计算,只需要将从后往前改为从前往后即可,时间复杂度O(VN)

多重背包问题
?

对于每个物品,可以拿不同的次数,如:有的1次,有的10 次,有的100次……

?

依然采取之前的二进制思想,简化问题

混合背包问题
?

对于一个背包问题,有多种物品可以选择:有只能拿一件的, 有可以拿多个的,有可以无限拿的,这时候应该怎么办?

这个问题综合了三种背包,代 表这个问题可以使用各种背包 问题的优化方法!

优化1
?

采用完全背包问题的优化方式1,即可瞬间去除大量无用物 品

?

P.S.:简直就是个垃圾清理器

优化2
?

先不考虑多重背包,只考虑01背包和完全背包,那么,就可 以用喜闻乐见的一维数组方法求解,只要在转移前判断下是 从前往后还是从后往前转移就行了,那么多重背包怎么办? 笨!用二进制转成多个01背包啊!

金明的预算方案(NOIP2006提高组)
题目描述 Description 金明今天很开心,家里购臵的新房就要领钥匙了,新房里 有一间金明自己专用的很宽敞的房间。更让他高兴的是, 妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布 臵,你说了算,只要不超过N元钱就行”。今天一早,金明 就开始做预算了,他把想买的物品分为两类:主件与附件 ,附件是从属于某个主件的,右图就是一些主件与附件的 例子。 如果要买归类为附件的物品,必须先买该附件所属的主件 。每个主件可以有0个、1个或2个附件。附件不再有从属 于自己的附件。金明想买的东西很多,肯定会超过妈妈限 定的N元。于是,他把每件物品规定了一个重要度,分为5 等:用整数1~5表示,第5等最重要。他还从因特网上查到 了每件物品的价格(都是10元的整数倍)。他希望在不超 过N元(可以等于N元)的前提下,使每件物品的价格与重 要度的乘积的总和最大。 设第j件物品的价格为v[j],重要度为w[j],共选中了k 件物品,编号依次为j1,j2,……,jk,则所求的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其 中*为乘号) 请你帮助金明设计一个满足要求的购物单。

主件 电脑 书柜

附件 打印机,扫描 仪 图书

书桌

台灯,文具

工作椅 无

输入描述 Input Description 第1行,为两个正整数,用一个空格隔开: N m (其中N(<32000)表示总钱数,m(<60)为希望购买物品的个数。) 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数 v p q (其中v表示该物品的价格(v<10000),p表示该物品的重要度(1~5),q表示该物品 是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所 属主件的编号) 输出描述 Output Description 只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000) 样例输入 Sample Input 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 样例输出 Sample Output 2200 数据范围及提示 Data Size & Hint 无

? ? ? ? ? ? ? ?

这题放眼望去应该是个树形dp,好可怕的说…… 不过好好看看还是能发现些什么的: 对于每个主件,它最多有2个附件,那么每个物品只有这几 种情况: 1.不带附件 2.带附件A 3.带附件B 4.带附件A和B 5.连主件都不拿

?

那么只要在状态转移时枚举每个物品拿还是不拿,拿几个附 件即可……

至此,背包问题全部完成!
但这仅仅是简单的背包问题而已

区间型DP
别看我看标题

石子归并
经典区间型dp

题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子, 一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使 得总合并代价达到最小。
?

输入描述 Input Description 第一行一个整数n(n<=100) 第二行n个整数w1,w2...wn (wi <= 100)
?

输出描述 Output Description 一个整数表示最小合并代价
? ?

样例输入 Sample Input

4 4114
?

样例输出 Sample Output

18
?

数据范围及提示 Data Size & Hint



分析下花费吧
?

花费是由两堆石子组成的,即: cost[i][j]=w[i]+w[i+1]+……+w[j-1]+w[j]

?

要合并i-j堆,必须要先合并i~k堆和k+1~j堆,可以得出递推式 js(i,j)= w[i] i=j

min( js(i,i) + js(i+1,j) …… js(i,j-1) + js(j,j) )+cost[i][j]

i≠j

然后怎么办?递归处理吗?
?

我说你百分百超时你信吗?

?

这节课学的啥?动态规划啊!开个数组,记录下来,直接转 成递推,时间复杂度O(n^2),完全无压力

?

P.S.:这个题写代码还是稍微有点难度的,所以写不出来的童 鞋可以考虑放(mei)弃(tian)本(yi)题(bian)

能量项链(noip2006)
?

题目描述 Description

在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链 上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标 记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子 的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸 盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才 能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前 一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r, 尾标记为n,则聚合后释放的能量为m*r*n(Mars单位),新产生 的珠子的头标记为m,尾标记为n。 需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能 量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得 到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放 出的总能量最大。

例如:设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5, 级玩意儿,拿这个代替下吧 10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示 第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后 释放的能量为: (4⊕1)=10*2*3=60

暂时找不到能量项链这种高

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710

?

输出描述 Output Description

只有一行,是一个正整数E(E≤2.1*109),为一个最优聚合顺序所释放的总能量。
?

样例输入 Sample Input

4

2 3 5 10
?

样例输出 Sample Output

710
?

数据范围及提示 Data Size & Hint



?

众所皆知,丝带项链是环形的,也就是说,这个题相比起石 子归并问题来说,变成了环形摆放,怎么办呢poi?

?
?

用脑子想一想,可以想出:即使是一个环合并,也不会合并 超过2圈
也就是说,可以把这串项链看作2倍长,读入时就进行预处 理,之后合并时只要找出在其中一点断开能得到的项链的最 大能量值就可以了

乘积最大
NOIP2000

?

题目描述 Description

今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚 先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力 竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动 的选手出了这样一道题目: 设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种 分法,使得这K+1个部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:312, 当N=3,K=1时会有以下两种分法:

1) 3*12=36
2) 31*2=62 这时,符合题目要求的结果是:31*2=62 现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。 输入描述 Input Description 程序的输入共有两行:

?

第一行共有2个自然数N,K(6≤N≤40,1≤K≤6)

第二行是一个长度为N的数字串。

?

输出描述 Output Description

结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。

?

样例输入 Sample Input

4 2 1231 样例输出 Sample Output

?

62 数据范围及提示 Data Size & Hint

?

本题由于比较老,数据实际也比较小,用long long 即可通过

?

这个题目要求用指定的乘号数量分开一个数,将它变得尽可能大,先找递 推式:
a[i][j][k]=max(a[i][i][k-1]*a[i+1][j][k-1]……a[i][j-1][k-1]*a[j][j][k-1])

?

a[i][j][k]的含义为:从i到j段,使用了k个乘号所产生的最大乘积,还可以 简化为a[i][k],含义为从1到i段使用了k个乘号所产生的最大乘积 记录到dp数组里进行动态规划就好了

?

数的划分(NOIP2001)
? ?

题目描述 Description 将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑 顺序)。

?
?

例如:n=7,k=3,下面三种划分方案被认为是相同的。
115

?

151
511

? ?

问有多少种不同的分法。

?

输入描述 Input Description

输入:n,k (6<n<=200,2<=k<=6)
?

输出描述 Output Description

输出:一个整数,即不同的分法。
?

样例输入 Sample Input

73
?

样例输出 Sample Output

4
?

数据范围及提示 Data Size & Hint

{四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

?

这个题目需要让人感到猎奇(← ←不要想歪)的动态规划: 对于一个数的划分方式,我们可以分为两种: 1.划分的结果中有数字1的 2.划分的结果中没有数字1的

? ? ?

?

对于会产生数字1的划分结果,我们可以忽略掉那个1,那么,n划分成m 部分有多少种方法等于n-1划分成m-1部分有多少种方法, 对于不产生数字1的划分结果,我们有另一种巧♂妙的办法:所有划分产 生的数字统一减1,那么, n划分成m部分有多少种方法等于n-m划分成m 部分有多少种方法 dp[i][j]=dp[i-1][j-1]+dp[i-j][j]

?

“ 总的来说,区间型dp要比背包型
dp难一些,所以下面来点简♂单 的dp



序列型dp
——传说中最水的dp

最长上升子序列
?

题目描述 Description

?

样例输入 Sample Input

给一个数组a1, a2 ... an,找到最长的上 升降子序列ab1<ab2< .. <abk,其中 b1<b2<..bk。 输出长度即可。

5 93627 样例输出 Sample Output

? ?

输入描述 Input Description

3

第一行,一个整数N。 第二行 ,N个整数(N < = 5000) 输出描述 Output Description
?

数据范围及提示 Data Size & Hint

【样例解释】
?

最长不下降子序列为3,6,7

输出K的极大值,即最长不下降子序列的 长度


这题还用讲么?
RT



我的做法是开一个dp数组,记录下以该数字为开头且带有该数字的最长上升子序列 的长度,应该没有和我一样的……

合唱队形(NOIP2004)
?

题目描述 Description

N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排 成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的 身高分别为T1,T2,…,TK, 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下 的同学排成合唱队形。 输入描述 Input Description 输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第一 行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘 米)。 输出描述 Output Description

? ?

?

输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。

?

样例输入 Sample Input

8 186 186 150 200 160 130 197 220 样例输出 Sample Output

?

4 数据范围及提示 Data Size & Hint

?

对于50%的数据,保证有n<=20;

对于全部的数据,保证有n<=100。

算法1
?

这道题要求百摆成合♂唱队形,即前面一段单调递增,后面 一段单调下降的序列

?

于是就有了算法1:枚举队伍中的最高点,前后的队伍分别 求最长上升子序列和最长下降子序列,时间复杂度 O(n*2*n^2)=O(n^3)
虽然不超时,但是敲起代码来有点麻烦额……

?

算法2:
?

既然要枚举每一个点,不如直接求出以每个点为开头或结尾 的最长上升和最长下降子序列,然后直接for一遍找出二者相 加的最大值再减去1(因为队伍只有一个最高点……)即可~
代码简化了不少,而且时间复杂度压到了O(n^2)!

?

“ 大家都知道最长公共子序列和最
长严格上升子序列吧~都是大水 题吧~
总有些不好的预感额……



“ 但是如果将两者结合起来呢?

那就是LCIS(Longest Common Increasing Subsequence)——最 长公共严格上升子序列!
果然来了……



?

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子 序列,再让他们研究了最长公共子序列,现在又让他们要研究最长公共上升子序列了。 小沐沐说,对于两个串A,B,如果它们都包含一段位臵不一定连续的数字,且数字是严 格递增的,那么称这一段数字是两个串的公共上升子串,而所有的公共上升子串中最长 的就是最长公共上升子串了。

奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子串。不过,只要告诉奶牛 它的长度就可以了。
输入描述 Input Description

?

第一行N,表示A,B的长度。 第二行,串A。 第三行,串B。 输出描述 Output Description

?

输出长度。

?

样例输入 Sample Input

4 2213

2123
样例输出 Sample Output

?

2 数据范围及提示 Data Size & Hint 1<=N<=3000,A,B中的数字不超过maxlongint

? ?

这题说实话我也不大会……
不过我还得硬着头皮讲……

?

好吧正题开始:dp[i][j]表示a串前i个数和b串前j个数且以b 串第j个数结尾的最长公共严格上升子序列(好绕口……以后就 叫LCIS了)LCIS的长度,然后根据最长公共子序列一题的状态 转移方程式可以得出本题的状态转移方程式:

dp[i][j]=dp[i-1][j]
dp[i][j]=max(dp[i-1][k])+1
?

(a[i]!=b[j])
(a[i]==b[j]&&a[k]<b[j])

应该不是很难懂……填充dp数组不用我教了吧……
恭喜各位完成序列型dp~

?

棋盘型dp
最终boss前的最后一个dp

?

过河卒
大水题一枚

A 点有一个过河卒,需要走到目标 B 点。 卒行走规则:可以向下、或者向右。同 时在棋盘上的任一点有一个对方的马 (如上图的C点),该马所在的点和所 有跳跃一步可达的点称为对方马的控制 点。例如上图 C 点上的马可以控制 9 个 点(图中的P1,P2 … P8 和 C)。卒不 能通过对方马的控制点。

?

棋盘用坐标表示,A 点(0,0)、B 点 (n,m)(n,m 为不超过 20 的整数,并 由键盘输入),同样马的位臵坐标是需要 给出的(约定: C不等于A,同时C不等 于B)。现在要求你计算出卒从 A 点能 够到达 B 点的路径的条数。
1<=n,m<=15

?

? ? ?

卒走到一个格子的方式只有两种: 1.从它左边的格子过来 2.从它上面的格子过来 那么,走到这个格子的方法数=走到上 面格子的方法数+走到左边格子的方法 数

水水就过了呗

?

骑士游历
NOIP1997

题目描述 Description 设有一个n*m的棋盘(2≤n≤50,2≤m≤50),如下 图,在棋盘上有一个中国象棋马。 规定: 1)马只能走日字 2)马只能向右跳 问给定起点x1,y1和终点x2,y2,求出马从x1,y1出 发到x2,y2的合法路径条数。 输入描述 Input Description 第一行2个整数n和m 第二行4个整数x1,y1,x2,y2 输出描述 Output Description 输出方案数 样例输入 Sample Input 30 30 1 15 3 15 样例输出 Sample Output 2

数据范围及提示 Data Size & Hint 2<=n,m<=50

? ?

不就是改改状态转移方程式啊 这个还不会的话还要不要来Loi啊

和过河卒有 什么区别额

传纸条(NOIP2008)
?

题目描述 Description

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班 上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就 无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方 手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到 小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以 帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在 小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心 程度没有定义,输入时用0表示),可以用一个0-100的自然数来表示,数越大表示越好心。小 渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两 条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

?

输入描述 Input Description

输入的第一行有2个用空格隔开的整数m和n,表示班里有m行n列(1<=m,n<=50)。
接下来的m行是一个m*n的矩阵,矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。 每行的n个整数之间用空格隔开。

?

输出描述 Output Description

输出共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

?

样例输入 Sample Input

33 039 285 570 样例输出 Sample Output 34 数据范围及提示 Data Size & Hint 30%的数据满足:1<=m,n<=10

100%的数据满足:1<=m,n<=50

0 3 9 2 8 5 5 7 0



大家有什么想法呢?



?

首先,我们可以轻松的得到一个错误的算法:跑两遍数字三角形,很明显这个算 法是错误的:因为有可能出现重复的路径,那么,这个算法就没用了吗? 当然不是的!我们这个算法的想法是:先找出好心值最高的路径,然后归零,找 好心值次高的路径,但是这样会导致出现重复路径,那么我们稍微改一下这个算 法:让两人同时找好心值最高的路径 那不就乱♂套了了吗?! 所以,我们要改一下这个方法:让两人同时从左上角到右下角走,这样的话只要 两人不走到同一个格子上(起点和终点除外),那么这条路径就是可行的! dp[i][j][k][l]分别记录纸条A和纸条B所在的位臵,转移时考虑4种情况: 1.A纸条向右,B纸条也向右

?

? ?

? ?

?
? ?

2.A纸条向右,B纸条向下
3.A纸条向下,B纸条也向下 4.A纸条向下,B纸条向右


可是还能再优化不是吗?


由于两张纸条移动的格子数是相同的,所以他们一定在同一条斜线上,所以dp数组 优化到三维:i,j,k分别表示走过的格子数,纸条A所在的行,纸条B所在的行,这样, 三维数组就可以表示出状态来,而且还减去了许多无用的状态~

最終鬼畜道化師ドナルドール?M【リアレン ジ】

树形DP&状压DP&DP骗分 (仅简单讲解)

? ?

顾名思义,在树上进行的DP 郑州学习时应该有讲过…… 由于这一部分的题目我也不太会,所以每一部分只讲一题……

?

树形DP

?

题目描述 Description

Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们的关系就像一 棵以校长为根的树,父结点就是子结点的直接上司。每个职员有一个快乐指数。现 在有个周年庆宴会,要求与会职员的快乐指数最大。但是,没有职员愿和直接上司 一起与会。 输入描述 Input Description

?

第一行一个整数N。(1<=N<=6000) 接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。 输出描述 Output Description
?

输出最大的快乐指数。

没有上司的舞会

?
? ? ? ? ? ? ? ? ?

样例输入 Sample Input
7 1111111 13 23 64 74 45 35 00 样例输出 Sample Output 5

?

?

? 这道题的评级是Diamond钻石

度的题……

,怎么看也不是noip提高难

? 不过我还是得讲……

? 对于一个职员来说,他只有两种状态:参加,不参加;有些

人是不是想到状压那边去了……看本题数据范围啊!6000啊!

? 那么,这题是不是就不可解了呢?

嘛,这也是道很经典的树形DP题目了

? 不然为啥要出这道题…… ? 对于一个职员来说,他要么来,要么不来,如果他来,那么

他的下属就一个都不敢来……(这是废话,如果你的班主任天 天去逛银座,那么你还敢去银座吗?)

? 于是,我们可以这样做:

为啥到了关键时候就翻页……

当然可以解!

? ?

开数组dp[6000][2],dp[i][0]代表i号职员不来时能得到的快乐值, dp[i][1]则代表i号职员来时能得到的最大快乐值 当这个人不来时,对他的下属是没有影响的,或者说,他的下属爱来来, 不爱来不来……所以可得:dp[i][0]=max(dp[k][0],dp[k][1]),这里的k 代表他的所有下属。因为他不来,他的下属来不来都行,而且对他的上 司又没有影响,所以我们可以贪心的找最大的; dp[i][1]=dp[k][0]+a[i],k依然代表他的所有下属。如果他来了,那么他 的下属就都不能来,所以就是他的下属全都不来的最大快乐值加上他的 快乐值。 这样就好做了~ DFS一遍求出所有人的快乐值,可以证明,最后产生的图形一定是一棵树, 所以,只要最后找出这个公司的超级大BOSS,并且找出他来和不来两个 状态快乐值最大的那个,这个题就AC啦~ P.S.:简直累人

?

? ?

?

?

旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行 推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅 行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城 市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是 要求得的路径路程为所有路径之中的最小值。 这个有点难懂额…… 没关系,codevs上就有这个题!

? ?

状压DP——TSP问题

?

题目描述 Description

有一个送外卖的,他手上有n份订单,他要把n份东西,分别送达n个不同的客户的手上。n个 不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发,然后n个城市都要走一次 (一个城市可以走多次),最后还要回到0点(他的单位),请问最短时间是多少。现在已知 任意两个城市的直接通路的时间。 输入描述 Input Description

?

第一行一个正整数n (1<=n<=15) 接下来是一个(n+1)*(n+1)的矩阵,矩阵中的数均为不超过10000的正整数。矩阵的i行j列表 示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b 到城市a的直接通路时间不一定相同,也就是说道路都是单向的。 输出描述 Output Description

?

一个正整数表示最少花费的时间

?

样例输入 Sample Input

3 0 1 10 10 1012 10 1 0 10 10 2 10 0 样例输出 Sample Output

?

8
数据范围及提示 Data Size & Hint

?

1<=n<=15

? ?

这个题的特点是:N特别小!

当然,N如果不小的话状压是做不了的……状压的题目数据一般不会超过 15,一会儿你就知道这是为什么了……

这个题有什么特点呢?

?

没什么办法,只能枚举这个高中不好好上,考不上大学,长大了只能送 外卖的倒霉孩子经过了哪几个城市来进行状态转移,反正一个城市只有 两种状态:经过和没有经过,那么,有没有想起和刚才那题一样的地方?
开15维数组记录下每个城市是否经过了!

?

?
? ?

笨!
15维数组我看你怎么维护! 既然已经压成二进制数了,为什么不再转成十进制数来开数组呢?

?

没错,这就是状压dp的数据特别小的原因!

对于这个题,我们有什么办法呢?

?

开数组dp[65536][16],dp[i][j]的含义是,经过了!@#¥%……&*城市, 目前处于第j个城市时走过的最短距离……最后需要求的是经过了所有的 城市后回到第一个城市时的最短距离…… 代码实现的话用位运算吧……

?

此题无节操

?

题目描述 Description

王钢是……(此处略去一些无用信息……) 地鼠游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时,会在地板上一下子冒出很多地鼠来,然后等你用榔头去敲击这些地鼠,每个地鼠被敲击 后,将会增加相应的游戏分值。问题是这些地鼠不会傻傻地等你去敲击,它总会在冒出一会时间后又钻到地板下面去(而且再也不上来),每个地鼠冒出 后停留的时间可能是不同的,而且每个地鼠被敲击后增加的游戏分值也可能是不同,为了胜出,游戏参与者就必须根据每个地鼠的特性,有选择地尽快敲 击一些地鼠,使得总的得分最大。 这个极具挑战性的游戏王钢特别喜欢,最近他经常在星期天上午玩这个游戏,慢慢地他不但敲击速度越来越快(敲击每个地鼠所需要的耗时是1秒),而 且他还发现了游戏的一些特征,那就是每次游戏重新开始后,某个地鼠冒出来后停留的时间都是固定的,而且他记录了每个地鼠被敲击后将会增加的分值。 于是,他在每次游戏开始后总能有次序地选择敲击不同的地鼠,保证每次得到最大的总分值。
?

输入描述 Input Description

输入包含3行,第一行包含一个整数n(1<=n<=100)表示有n个地鼠从地上冒出来,第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间,第三 行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值(<=100)。每行中第i个数都表示第i个地鼠的信息。
?

输出描述 Output Description

输出只有一行一个整数,表示王钢所能获得的最大游戏总分值。
?

样例输入 Sample Input

5
5 3 6 1 4 7 9 2 1 5
?

样例输出 Sample Output

地鼠游戏

24

?

RT,原版的数据范围是200000,正解是贪心+堆,时间复杂度O(NlogN) 但是dp只能做到O(n^2) 不过,这是codevs嘛~,这数据简直太良心啦hhh

?

这个题是用DP骗过去的……

?

开二维dp数组,dp[i][j]是在第i只地鼠,时间已过去j秒时可以拿到的最 大得分,开始先排遍序,然后像背包一样转移就行啦~

?

对于有些题目来说,dp可能不是正解,但是,dp可以骗分,有些题的数 据就是30%暴力,60%DP,100%正解,dp全对的题也是noip每年必考 的内容,所以,学好DP,对大家的帮助是非常大的~

终于讲完了!
? 那么,DP部分就告一段落吧,喜欢刷(zi)题
(nve)的同(dou)学(M)如果需要题目的话,我会 给你找一些喜(jie)闻(cao)乐(sang)见(shi)的题目 的!


相关文章:
信息学奥赛-动态规划测试讲解_初中其他_教学视频大全
16道测试习题的讲解在期末作业里可以下载到测试题目和标程由于数据量太大,没有...目录(共1章) 第1章 本章的标题 01 信息学奥赛-动态规划测试讲解 108分钟 ©...
信息学奥赛-动态规划测试讲解_初中其他_教学视频大全
16道测试习题的讲解在期末作业里可以下载到测试题目和标程由于数据量太大,没有...目录(共1章) 第1章 本章的标题 01 信息学奥赛-动态规划测试讲解 108分钟 ©...
信息学奥赛——算法入门教程
信息学奥赛——算法入门教程_其它语言学习_外语学习_教育专区。全国青少年信息学...分治法、动态规划法等算法中都可以使用递归思想来实现, 从而使编写的程序更加...
信息学奥赛——树型动态规划的实例分析
信息学奥赛——树型动态规划的实例分析_一年级语文_语文_小学教育_教育专区。信息...[问题描述] 在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些...
动态规划
动态规划信息学奥赛中的应用 吴孝燕 一、动态规划的基本思想 动态规划策略通常用于求解具有某种最优性质的问题。动态规划法与分治法类似,其基 本思想也是将待求解...
贪婪的动态规划
字】贪心法,动态规划,状态,时间复杂度 【摘要】贪心法和动态规划信息学竞赛中的两种常用算法, 本文着重讨论了贪心的 思想是如何巧妙的运用到动态规划的解题中的...
NOIP复习(动态规划)
NOIP复习(动态规划)_工学_高等教育_教育专区。NOIP复习(动态规划) [NOIP 复习]第三章:动态规划分类: NOIP Wikioi ACM-ICPC/蓝桥杯/其他大学竞赛 动态规划 2014...
2011年信息学奥赛 动态规划题模拟(奥赛精选系列)_免费...
2011年信息学奥赛 动态规划题模拟(奥赛精选系列)2011年信息学奥赛 动态规划题模拟...活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度 N 的...
高中计算机竞赛 编程 动态规划解析辅导
99 三、多姿多彩的动态规划动态规划是一种重要的程序设计思想, 具有广泛的应用价值, 在信息学竞赛中经常出现。 使用动态规划思想来设计程序, 对于不少问题的解决...
信息学竞赛题库
做其中的搜索,动态规划,字符串 5,大榕树(福建师大附中信息学竞赛网站) http://www.mydrs.org/dvp/index.php 对参加全国青少年信息学奥赛(NOI,NOIP)有所帮助....
更多相关标签:
信息学奥赛动态规划 | 初中信息学奥赛试题 | 初中信息学奥赛 | 高中信息学奥赛 | 信息学奥赛 | 信息学奥赛一本通 pdf | 小学信息学奥赛 | 信息学奥赛一本通 |