动态规划基础和建模

动态规划基础和建模

山东省潍坊第一中学秦政

clavichord

前言

*动态规划是统筹学的重要内容

*动态规划是01的重要内容

*据不完全统计，每次考试动态规划起码有一道题

髡.

前言

*这个课件的目的：

*对动态规划的模型进行了一些总结

*有部分内容超出了NOIP范围

*为同学们提供一个刷题的方向

*请同学们踊跃发言

动忐规划的基本概念

*阶段

*状态

*决策

*状态转移

*状态转移方程

动忐规划的基本概念

*最优子结构

*无后效性原则

动忐规划的基本概念

动忐规划的基本概念

*实现方式：

*递推：顺推和逆推

*记忆化搜索

*前者灵活，优化方法多

*后者可以减少不必要节点的计算

动忐规划的基本概念

*时间复杂度：

*状态数*转移费用

动忐规划的模型

*线性模型

*区间模型

*矩形模型

*树形模型

*背包模型

*图状模型

*SCDP

*多线程DP

*多重DP

*更广泛的

线性模型

*单线问题：

*上楼梯问题

*LIS问题

*乌龟棋

*诗人小G（简化版）

*双线问题：

*LCS问题

*模糊匹配

上楼梯问题

*Zbwmqlw神薜要上楼梯，他一次可以上一层，也可

以两°

*楼梯有n层

二有多少种上楼梯的方案

上楼梯问题

*N<=10A7?

*设f[i]表示到第i层得方案数

*前一步可以上一层也可以上两层

*F[i]=f[i-i]+f[i-2]

*N<=10A15?

*矩阵乘法

US问题

*给定一个数列{an},求它的一个子序列{bm}

*满足bi〈b2〈b3<・・・<bm

*使得m最大

*N<=10000

US问题

*设f[i]表示以i结尾的US的长度

*F[i]=max{f[j]]+i,j<iJLa[j]<a[i]

*时间复杂度？0（n八2）

*如何优化?

US问题

*对于i来说，如果存在一个长度为len的US以i结尾,

那么也一定存在长度<len的

*即：满足单调性！

*设g[i]表示的]二i的最小的a[j]

*二分g[k]>=a[i]的最大的k

*F[i]=k+1

*时间复杂度O(nlogn)

乌龟棋CN0IP20WtJ

♦有一行长度为n+1的格子，编号。到n+1,要从第。个

格子的左边出发，到达第n个格子停止。每次可以向

右移动1到4格，分别可以操作G次

♦求方案数

*保证£七1Q*i=n

♦数据范围：n<350,Ct<40

乌龟棋

*F[i][a][b][c][d]表示到位置i,四种操作分别进行了

a,b,c,d次

决策有四种

*时间复杂度：0(ncA4)

*TLE+MLE

乌龟棋

♦=n

*通过a,b,c,d可以推出1

*F[a][b][c][d]

*四种决策

*0(CA4)

诗人小GCNOI2OO9J简化板

----.JBBBIgjjf

*一首诗包含了若干个句子，对于一些连续的短句，’…

可以将它们用空格隔开并放在一行中，注意一行中

可以放的句子数目是没有限制的。小G给每首诗定

义了一个行标准长度（行的长度为一行中符号的总

个数），他希望排版后每行的长度都和行标准长度

相差不远。显然排版时，不应改变原有的句子顺序，

并且小G不允许把一个句子分在两行或者更多的行

内。在满足上面两个条件的情况下，小G对于排版

中的每行定义了一个不协调度,为这行的实际长度与

行标准长度差值绝对值的P次方，而一个排版的不协

调度为所有行不协调度的总和。

*小6最近又作了几首诗，现在请你对这首诗进行排

版，使得排版后的诗尽量协调（即不协调度尽量

小），并把排版的结果告诉他。

诗人小G

*F[i]表示前i句诗的最小不协调度

*F[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)Ap)

*时间复杂度0(nA2)

*优化？

*导数证明四边形不等式，有兴趣的同学自己查阅有

关资料

LCS问题

*给定两个字符串S,t

*求最长公共字串

*例：abcde和ace的LCS是ace

*N<=1000

LCS问题

*设可][口表示第一个串到i,第二个串到j的LCS

*F[i][j]=f[i-1][H]+1,s[i]<j]

*=min{f[i-i][j],f[i][M]},s[i]!=t[j]

*时间复杂度0(nA2)

模糊匹配（POJ1229）

*给定两个字符串s和t,每个字符串有英文字母和*?!

组成，*?!的含义分别是：

**:匹配一个或多个字符；

*?:匹配至少一个至多三个字符；

*!:匹配至少三个字符。

*问两个字符串是否能够匹配。

*N<=1000

模糊匹配

耒重新定义通配符：

♦匹配一个字符；

*#:匹配一个字符或者为空；

♦$:匹配任意个字符或者为空。

♦那么，题目中的三种通配符，我们可以转化成这样：

**T@$

♦?T@##

*!T@@@$

*然后，我们设了田田表示第一个字符串的前i个和第二个

字符串的前j个能否匹配，那么，我们可以分情况转移

*与上一道题类似

*时间复杂度。（口?）。

区间模型

*石子归并

*回文词

决斗问题

*Blocks

石子归并

*有n堆石子，第i堆重a[i]

*每次可以合并相邻两堆

*合并费用为新堆的重量

*求合并成一堆的最小费用

*N<=200

石子归并

*合并的费用是一段的和

*设孔口口]表示合并i到j的一段

*F[i][j]=min{f[i][k]+f[k+i][j])+sum[i][j]

*时间复杂度0(r1A3)

回文词CI0I2000J

*给定一个字符串S,要求添加最少的字符，使得s成

为一个回文串。

*N〈二5。00

回文词

*abcba:回文

*abcbc:不回文

*表示i到j变成回文的最小代价

*F[i][j]<i+1][H],s[i]=s[j]

*=min{f[i+i][j],f[i][j-i]}+i,s[i]!=s[j]

*时间复杂度0（n八2）

决斗问题CPOI99J

*1\1个人排成一圈，他们要决斗N-1场，其中相邻的两

人决斗（即第i个人与第i+1个人决斗，第N个人与第1

个人决斗），死者退出，最终剩下的人胜利。将任

意两个人之间决斗的输赢情况告诉你，决斗顺序由

你安排，问哪些人可能成为最终的胜利者？

*N<=200

决斗问题

*首先把环复制一份接到后面

*然后一个人获胜就是跟自己相遇

*表示i能j相遇

*Meet[i][j]=meet[i][k]&&meet[k][j]&&(beat[i][k]||

beat[j][k])

*时间复杂度0(口八3)

BlocksCPOJ139OJ

♦现在有一个长度为n的方块序列，每个方块有一个颜

色，现在相邻的相同颜色的方块可以消除，把长度

为I的方块消除的得分为求消除所有方块的最大

得分。

Blocks

*我们可以选择保留一部分不消除，而跟前面相同颜

色的合并起来一起消除以获得更大的费用，所以再

设计状态时，我们需要把后面留下的一起考虑进去。

*首先我们把相邻的相同颜色的缩成一段，len[i]表示

第i段的长度

*记pre[i]表示第i段往前第一个与i颜色相同的段的编号

Blocks

*设小田工灯表示把从第i段到第j段，最后面有长度为k

的与j颜色相同的消去的最大得分

*F[i][j][k]=max[f[i][j-i][o]+(len[j]+k)A2,

*f[>][P^[j]][len[j]+k]+f[pre[j]+i][j][o]]

*记忆化搜索实现效率高

头巨形模型

*降维拆成链：滑雪

*子矩形：采油区域

*行列：棋盘分割

*对角线：转纸条

滑雪CSHTSC2002；

*Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。

可是为了获得速度，滑的区域必须向下倾斜，而且

当你滑到坡底，你不得不再次走上坡或者等待升降

机来载你。Michael想知道载一个区域中最长的滑坡。

区域由一个二维数组给出。数组的每个数字代表点

的高度。

滑雪

♦对于每一个点，只能转移到更高的地方：

*f[i]Q]+1T砌叫+1/]>h[i]D]X|i-f|+

lj一j'l=1

*所以海拔高度具有很强的阶段性。于是我们考虑把

所有的格子取出来，排个序，这就成了一个线性的

模型。如果用一个堆的话实现起来更简单。

*时间复杂度O(n21ogn2)。

采油区域CAPIO2OO9J

*Siruseri政府决定将石油资源丰富的Navalur省的土地

拍卖给私人承包商以建立油井。被拍卖的整班土地

为一个矩形区域，被划分为MxN个小块。Siruseri地

质调查局有关于Navalur土地石油储量的估测数据。

这些数据表示为MxN个正整数，即对每一小块土地

石油储量的估计值。为了避免出现垄断，政府规定

每一个承包商只能承包一个由KxK块相连的土地构

成的正方形区域。AoE石油联合公司由三个承包商组

成，他们想选择三块互不相交的KxK的区域使得总

的收益最大。

采油区域

*一共只有六种情况:

采油区域

案一共只有上面的六种情况，对于这六种情况，我们

分别要雍护：

*以某个点为右上角的矩形内的kxk的最大值ru[i][j]

*以某个点为左上角的矩形内的kxk的最大值

*以某个点为右下角的矩形内的kxk的最大值

*以某个点为左下角的矩形内的kxk的最大值

*两的条竖线之间的kxk的最大值

*两条横线之间的kxk的最大值门

采油区域

*对于前四个值，我们类似的转移，下面以HJ的转移为例：

*ru[i][j]=

max{ru[i-1][j],ni[i][j-1],sum[i-k+l][j—k+l][i]Q]]

*sum[xl][yl][x2][y2]可以通过子矩形和来0(1)维护，这样

维护这四个瓦是0(nm)的。

采油区域

♦对于后面两个，我们需要记录每行和每列的ru最大

值r[i]和c[i],会个可以在计算ru的时候同时维护。

cm新rm而强移，也是类似的，这里以cm为例：

*cm[i][j]=max{cm[i]Q-l],c[j])

*这样我们通过枚举分割线，利用上面维护的值就可

以计算出答案了。时间复杂度O(nm)。

棋盘分割（NOI99J

*将一个8*8的棋盘进行如下分割：将原棋盘割下一

块矩形棋盘并使剩下部分也是矩形，再将剩下的部

分继续如此分割，这样割了n-1次后，连同最后剩下

的矩形棋盘共有n块矩形棋盘。（每次切割都只能沿

着棋盘格子的边进行。）

允许的分割方案不允许的分割方案.

棋盘分割

♦原棋盘上每一格有一个分值，一块矩形棋盘的总分

为其所含各格分值之和。现在需要把棋盘按上述规

则分割成n块矩形棋盘，并使各矩形棋盘总分的均方

差最小。均方差。=乒3亘，其中平均值

元=卓岩，修为第i块矩形棋盘的总分。请编程对给

出的矗及n,求出。的最小值。

棋盘分割

*我们从要计算的值入手。

*我们可以发现，元的值是一定的。我们把O平方，得

到：a2n=-x)2,我们要使o最小，等价于

使02rl最小。把。2九展开，得到：

*a2n=£仁1(蛭-2xtx+x2)=£21(痣-2%㈤+

x2n

棋盘分割

*于是，我们就要使骞1式靖-2*送)最小。设

f[i][xl][yl][x2]|y2]裘示把(xl,yl,x2,y2)的矩形分成i份的

(a―24。的最小值，那么：

*f[i][xl][yl][x2][y2]=min{

♦f[l][xl][yl][x2]y]+f[i-1][xl]V+I][x2][y2],

*f[i-+f[l][xl][y7+I][x2][y2],

♦f[l][xl]|yl][xr][y2]+f[i-l][x7+1][yl][x2][y2],

*f[i-1][xl][yl][xl[y2]+f[l][xf+1][yl][x2][y2]]

♦时间复杂度0(81)。

传纸条CNOIP2OO8TJ

♦给定一个nxm的矩形，每个格子里有一个数。现在

求从左上角到右下角的两条不相交路径，使经过的

格子的和最大。

传纸条

♦因为是在矩形里的两条路径，考虑按照步长划分阶

段。

・我们需要记录两条路径的位置，可以发现，因为步

长已经定了，所以只要知道横坐标，纵坐标就可以

推出来。于是，我们设表示步长为i,第一条

路径横坐标为j,第二条路径的横坐标为k的最大和，

因为两条路径可以交换，而这是没有意义的，所以

我们限定jvk,那么：

传纸条

*f[Wk]=

max^U-l][j-l][k--l][/][fc],

*f[i-l]U-l][k]J[i-l][j]lk-1])

*上面的方程转移时要注意判断两条路径不能走到一

块去和不能走到矩阵外面去。

*时间复杂度0(n3)。

树形模型

*数值分配型：选课，贪吃的九头龙

*多叉转二叉

*树形背包

*位置转移型：CellPhoneNetwork

*链划分型：树的最长链

*可转化成区间模型和线性模型：加分二叉树

选课CCTSC99J

*在大学里每个学生，为了达到一定的学分，必须从

很多课程里选择一些课程来学习，在课程里有些课

程必须在某些课程之前学习，如高等数学总是在其

它课程之前学习。现在有N门功课，每门课有个学分,

每门课有一门或没有直接先修课（若课程a是课程b

的先修课即只有学完了课程a,才能学习课程b）o

一个学生要从这些课程里选择M门课程学习，问他

能获得的最大学分是多少？

*如果要选课程a必须要选课程b,那么就在a和b之间

连边，这样，得到的会是一个森林。于是我们添加

一个节点o,学分为o,把这个森林连成树，于是问

题就是从一颗n+1个节点的树里选m+1个节点，使得

总分最大。这样，点o是必须选的。

*设£国[j]表示以i为根的子树中选j个的最大得分，那么:

*f[i][j]=max堡裁葡[子f冈3]}

*这个用树形背包实现的话会异常方便。

*考虑边界。对于一个点,f[i][O]=O,f[i][l]=w[i],

其余的都是-Infinity。

*时间复杂度是0(nm2)的。

贪吃的九头龙（NOI2OO2）

*传说中的九头龙是一种特别贪吃的动物。虽然名字

叫“九头龙”，但这只是说它出生的时候有九个头，

而在成长的过程中，它有时会长出很多的新头，头

的总数会远大于九，当然也会有旧头因衰老而自己

脱落。

*有一天，有M个脑袋的九头龙看到一棵长有N个果子

的果树，喜出望外，恨不得一口把它全部吃掉。可

是必须照顾到每个头，因此它需要把N个果子分成M

组，每组至少看一个果子，让每个头吃一组。

贪吃的九头龙

*这M个脑袋中有一个最大，称为“大头”，是众头

之首，它要吃掉恰［张个果子,而且K个果子中理所

当然地应该包括唯一的一个最大的果子。果子由N-1

根树枝连接起来，由于果树是一个整体，因此可以

从任意一个果子出发沿着树枝“走到”任何一个其

他的果子。

贪吃的九头龙

*对于每段树枝，如果它所连接的两个果子需要由不

同的头来吃掉，那么两个头会共同把树枝弄断而把

果子分开；如果这两个果子是由同一个头来吃掉，

那么这个头会懒得把它弄断而直接把果子连同树枝

一起吃掉。当然，吃树枝并不是很舒服的，因此每

段树枝都有一个吃下去的“难受值”，而九头龙的

难受值就是所有头吃掉的树枝的“难受值”之和。

*九头龙希望它的“难受值”尽量小，你能帮它算算

吗？

贪吃的九头龙

*首先，如果k+m-l>m,也就是说果子不够吃，

显然无解。

*然后来看答案是如何组成的。

♦当M=2的时候，难受值的和是大头吃进去的树枝的

难受值+小头吃进去的难受值

♦当MN3的时候，我们把果子按照奇偶分层，让小头

们轮流吃就可以保证小头不会吃进去树枝，所以这

个时候难受值的和是大头吃进去的树枝的难受值。

*我们以大果子为根建树，同时把边上的权值推到下

面的节点上。

贪吃的九头龙

豪设表示以i为根的子树中，大头吃MSi被小头吃的装小值，

表示以i为根的子树中，大头吃Msi被大头吃的最小值，那么：

*f[i]0][O]=min?潦得儿子min[f[k][pfc][O]+xxw[矶f因[pfc][l]}

*f[iJD][l]=min。%鲨鼠子mto{f[对加+w伙]}

*„（0,?n=2

X=-11^>3

*考虑边界。如果在一个点大头不吃，那么显然是0,所以f[i][0][0]=0；

而如果大头吃，那么显然j的值必须是1,所以f[i][l][l]=0。其它的值都

是Infinity。

*时间复杂度WnnF）。

贪吃的九头龙

*我们从多叉转二叉的角度来看这道题

树的最长链

*给定一棵树，求树的最长链

树的最长链

*贪心做法：两次BFS

*证明

树的最长链

*动态规划：设f[i]表示儿子连上来的最长链，g[i]表示

儿子连上来的次长链，h[i]表示父亲来的最长链

*F[i]=max{f[j]]+1

*同时更新g[i]

*H[i]=max{f[p],h[p]]+I,f[p]>f[i]+1

*=max[g[p],h[p]}+i,f[p]=f[i]+i

CellPhoneNetworkCPOJ3659J

*给定一^果树，求树的最小点支配集。

*N<=10000

*支配集：点覆盖点

CellPhoneNetwork

*每个点有三个状态：被儿子覆盖，选自己，不被儿

子覆盖。

*设f［讥0］表示被儿子覆盖需要的最小点数，同口］表

示选自己的最小点数，f［讥2］表示不选自己，不被儿

子覆盖的最小点数，那么：

CellPhoneNetwork

*f[i][o]=min{嚷j的儿子f耐min{f[k][o],f[i][1])]

*闻M=£j是i的儿子min{f[j][o],f[j][i],f[j][2])

f[i][2]=Ej是j的儿子

*这样的复杂度是0(n2)的。

CellPhoneNetwork

*这个方程的瓶颈在第一个转移上，考虑维护

sum=£min{fO][o],f[j][i]},那么：

♦f[i][0]=min{sum-min[f[j][0],f[j][1]}+f[j][1]}

*这样，整个算法就成0(n)的了。

加分二叉树CNOIP2OO3J

*设一个n个节点的二叉树tree的中序遍历为（1,2万,..・刀），

其中数字1,2,5…,n为节点编号。每个节点都有一个分数

（均为正整数），记第j个节点的分数为di,tree及它的每

个子树都有一个务口分，任一棵子树subtree（也包含tree

本身）的加分计算方法如下：

*subtree的左子树的加分Xsubtree的右子树的加分十

subtree的根的分数

*若某个子树为主，规定其加分为1,叶子的加分就是叶

节点本身的分数。不考虑它的空

*子树。

*试求一棵符合中序遍历为（i,2,3,..・,n）且加分最高的二

叉树tree。要求输出；

*（1）tree的最高加分

*（2）tree的前序遍历

加分二叉树

♦本题乍一看像是一个树形模型，但是树的形态又不

确定，不能用树形模型的方法来做。

*设币］［j］表示从i到j的一段是一棵子树的最大加分，那

么：

♦f[i][j]=max{f[i][k-l]*f[k+l][j]+s[k]]

*时间复杂度0(n3)

*第二问：记录第一问的决策

背包模型

*部分背包

*01背包

*完全背包

*多重背包

*分组背包

*依赖背包

*泛化物品

背包问题

*给定一个容量为m的背包和n个物品，每个物品有一

个价值v和一个费用w,求在满足容量限制的情况下

最大化价值。

*NPC问题

部分背包问题

*特点：物品可以任意划分

*方法：求单位价值，贪心

01背包问题

♦特点：每种物品只有一个，要么取，要么不取

*设用田]表示前i个物品，容量为j的最大价值，很显然,

每个物品有取或不取两种决策：

*f[i][j]=max{f[i-l][j],f[i-l][j-cost[i]]+

value[i]]

*这个方法时间复杂度是O(rnn)的，空间复杂度是

O(rnn)的。

01背包问题

*空间优化：滚动数组

*代码：

*voidZeroOnePack{

*for(inti=i;i〈=n;i++)

*for(intj=m;j>=cost[i];j-)

*gmax(f[j],f[j-cost[i]]+value[i]);

*)

完全背包问题

*特点：每种物品有无穷多个

*f[i][j]=max{f[i-l]|j],f[i-l][j-cost[i]]+

value[i],f[i][j—cost[i]]+value[i]}

*代码：

*voidCompletePack{

*for(inti=i；i<=n;i++)

*for(intj=cost[i];j<=m;j++)

♦gmax(f[j],f[j-cost[i]]+value[i]);

*}

多重背包问题

*特点：每类问题有个数限制c[i]

*基本想法：每类物品的每一个看作一个物品，转化成01

背包

*代码：

*voidLimitedPack{

*for(inti=i;i〈=n;i++)

*for(intj=i;j<=limit[i];j++)

*for(intk=m;k>=cost[i];k-)

*gmax(f[k],f[k-cost[i]]+value[i]);

*}

多重背包问题

*优化：

*二进制拆分

*原理：2八k能够表示出0~2A(k+1>1的所有数

*把c[i]拆成若干2八k相力口

*O(nmlogc)

分组背包问题

*特点：物品被分为很多组，每组之间有限制。

*假设限制为：每组只能取一个

*F[i][j]=max[f[i-i][j],f[i-i][j-w[i][k]]+v[i][k]]

*代码：

*voidGroupPack{

*for(inti=i;i〈=n;i++)

*for(intj=m;j>=mincost[i];j-)

*for(intk=i;k<=cnt[i];k++)if(cost[i][k]<=j)

*gmax(f[j],f[j-cost[i][k]]+value[i][k];

*}

分配时间CWFTSC2009TJ

*考试的时候合理分配时间是很重要的，我们应该在

同样的时间内尽量得到更多的分数。现在有m道题

需要在n分钟内解决，每道题分为p个步骤，每道题

的每个步骤都会有不同的分值，所需时间也不尽相

同。现在你可以从任意一道题的任意一个步骤开始，

如果当前步骤与上一步骤不连续，则需要q分钟的思

考时间（每题第一个步骤之前同样需要思考），请

确定自己的策略使得获得的分数最高。

分配时间

*每道题实际上是一个组。

*我们可以发现，每个步骤选或不选对后面的决策是有影

响的，所以我们考虑加一维来区分。

*设耳口用小]表示前i道题的前j个步骤，其中第i道题的第j

个步骤被选，在k分钟内解决的最大得分，g[i][j][k]表

示前i道题的前j个步骤，其中第i道题的第j个步骤不被选,

在k分钟内解决的最大得分，那么：

分配时间

*f[i][l]M=max{f[i-l][p][k-q-t[i][l]],g[i-l][p][k-

q-t[i][l]}+s[i][l]

♦g[i][l][k]=max[f[i-1][p][k],g[i-1][p][k]}

♦f[i]D][k]=

max[f[i][j-l][k-t[i][j]]，5[i][/-l][k-q-t[i][/]]}+

s[i][f]

♦9[口皿k]=max{f[i][j-l][klg[i][j-l][k]}

♦时间复杂度O(nmp)。

依赖背包问题

*依赖背包问题，顾名思义，就是一些物品可以选要

建立在其它一些物品被选的基础之上。这类问题往

往是建立在树上的，所以通常也叫树形背包问题。

鉴于在树形模型中已经有了比较详细的讨论，这里

不再详细展开

泛化物品

♦背包问题的终极版

*泛化物品是指没有固定的费用和价值，其价值是关

于费用的函数。即：在容量为V的背包问题中，泛化

物品是定义域为0.,.V的函数h,当其费用为V时，其

价值为h(v)。

泛化物品

*voidGeneralMatters{

*for(inti=i；i<=n;i++)

*for(intj=m;j>=o;j-)

*for(intk=o;k<=j;k++)

*gmax(f[j],f[j-k]+cost(i,k));

*)

泛化物品

*回顾上面的数值分配型的树形动态规划，考虑其中

的一个节点i,其子树就相当于一个一个的泛化物品,

随着分配给它们的数值的变化，其价值也在不断的

变化。由此可见，泛化物品在各个方面都有着很广

泛的应用。

图状模型

*环状：

*Naptime

*拓扑图：

*关键路径

*一般图模型

最优贸易

环状模型

*找一个位置把环拆成链

*DP

*把链的首尾接成环

*枚举首状态

Naptime「POJ2228)

*小尸同学最近特别累，老是想睡觉

*小F同学把一天分为n个时段，选择不一定连续的m

个时段来睡觉

*小F同学睡眠质量不好，每次睡觉要花1个时段来进

入睡眠

*每个时段有一个休息值a[i],如果小F同学选择在[l,j]

的时段内睡觉的话,得到的休息就是a[i+i]+...+a[j],

因为时段i被用来进入睡眠了

*如何选择能够休息的最好？

*注意天与天是连续的，即这n个时段是一个环

naptime

*因为环首尾相接的地方会对结果产生影响，所以要枚举

开始的状态，做几遍DP

*设表示前i个时间段睡了j段，第i段不睡的最长时

间，的仃如装示第i段睡岛最长舟面,那么：

*f[i][j][o]=max{f[i-i][j][o],f[M][j][i])

*f[d[i][1]=max{f[i-i][M][o],f[i-i][j-i][i]+t[i]}

*初始时，所有的f二-INF

*然后枚举第一个时间段睡不睡，分别使

f[l][l][l]=1,f[l][o][o]=l,做两次DP

*内存限制比较紧,要滚动

拓扑图模型

*边拓扑排序边DP

*SCC缩点

关键路径

*给定一个DAG,求从s到t的最长路

关键路径

*设f[i]表示从s到i的最长路径

*F[i]+dis[i][j]->f[j]

*拓扑排序的过程中解决

最优贸易CNOIP2OO9TJ

*给定一个图，边有的是单向的，有的是双向的

*有一个水晶球，每个点有一个价格

*从5出发到t,沿途在某个点买入水晶球，在另一个点

卖出

*显然你要先买入才能卖出

*最大化收益

最优贸易

*方法一：

*同一个SCC里的点都可以走到，可以在其中任意一个

买，任意一个卖

*收缩SCC,记录SCC的最大值和最小值

*F[i]表示到i的最大获利，g[i]表示到i的最小价格，

minv[i]表示i所在SCC的最小价格，maxv[i]表示i所在

SCC的最大价格

*G[i]=min[g[j],minv[i]}

*F[i]=max{f[j],maxv[i]-g[i]]

*边拓扑排序边做

最优贸易

*方法二：

*F[i][o]表示到i点，没有水晶球的最大

*表示到i点,有水晶球的最大

*F[i][o]=max{f[j][o],f[j][i]+w[i]]

*f[i][i]=max{f[j]