动态规划例题讲解课件

动态规划例题讲解山东师大附中魏铭动态规划例题讲解山东师大附中1Preview本节课主要通过几道例题，总揽NOIp中较常见的动态规划模型，不会过多涉及优化内容。万丈高楼平地起Preview本节课主要通过几道例题，总揽NOIp中较常见的2Preview最长上升子序列内存碎片背包问题最长公共子序列石子合并括号序列决斗三取方格数选课贪吃的九头龙Preview最长上升子序列括号序列3最长上升子序列给出一个数列{a1,a2,...,an}，要求你选出尽量多的元素，使这些元素按其相对位置单调递增。SampleOutput4SampleInput9

5

8

9

2

3

1

7

4

6最长上升子序列给出一个数列{a1,a2,...,an}，要求4最长上升子序列算法：动态规划令f[i]表示以ai为结尾的最长上升子序列的长度转移方程：

f[i]=max(f[j],1<=j<i,a[j]<a[i])+1时间复杂度：O(N^2)最长上升子序列算法：动态规划5最长上升子序列换一种状态表示方法令f[i]表示长度为i的上升子序列的结尾数字最小是多少初始f[0]=-inf,f[i]=inf（inf为无穷大，可取值为大于任意ai绝对值的一个数字）最长上升子序列换一种状态表示方法6最长上升子序列F[0]F[1]F[2]F[3]F[4]初始-infinfinfinfinf插入a1后-inf5infinfinf插入a2后-inf58infinf插入a3后-inf589inf插入a4后-inf289inf插入a5后-inf239inf插入a6后-inf139inf插入a7后-inf137inf插入a8后-inf134inf插入a9后-inf1346SampleInput5

8

9

2

3

1

7

4

6最长上升子序列F[0]F[1]F[2]F[3]F[4]初始-7最长上升子序列f[]是单调递增的，因为如果有i<j且f[i]>=f[j]，那么f[i]必定可以被f[j]的方案所更新。每处理到一个ai，我们要找到一个k满足

f[k–1]<ai且f[k]>=ai，并用ai更新f[k]，最终max(k|f[k]!=inf)就是答案。可以通过二分查找将时间复杂度降至

O(NlogN)最长上升子序列f[]是单调递增的，因为如果有i<j且f[i]8选人将所有人按照智商排序，以情商为关键字，求最长上升子序列的长度即可。选人将所有人按照智商排序，以情商为关键字，求最长上升子序列的9内存碎片N个内存申请请求，申请长度为L[i]的内存块c[i]次。当程序申请长度为L的内存时，也可以给它分配一块长度为L’（L’>L）的更大的内存块。内存长度种类不超过K。求最少需要的内存。内存碎片N个内存申请请求，申请长度为L[i]的内存块c[i]10内存碎片SampleInput32

101

111

2013个内存申请最多2种长度SampleOutput42

方案：

两个11，一个20内存碎片SampleInputSampleOutput11内存碎片算法：动态规划先将所有L[i]排序。11234467822244

66

881133

666882

33377778这一行是内存申请的长度这三行是内存分配的可能长度内存碎片算法：动态规划这一行是内存申请的长度这三行是内存分配12内存碎片一种内存长度覆盖的区间必定是连续的，并且该内存长度等于覆盖区间最后一个内存申请操作的长度。令f[i,j]表示考虑完前i个内存申请操作，并且已经使用完j种内存长度的最少需要的内存。内存碎片一种内存长度覆盖的区间必定是连续的，并且该内存长度等13内存碎片f[i,j]=min{

f[k,j-1]+

(c[k+1]+c[k+2]+...+c[i])*L[i],0<=k<i}预处理sc[i]=c[1]+c[2]+...+c[i]f[i,j]=min{

f[k,j-1]+(sc[i]-sc[k])*L[i],0<=k<i)}时间复杂度O(N^2*K)内存碎片f[i,j]=min{

f[k,j-1]+

(c[140/1背包问题共有N件物品，每件物品有一定的重量w[i]和一定的价值v[i]，现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=100000/1背包问题共有N件物品，每件物品有一定的重量w[i]和一150/1背包问题SampleInput3100

30300

801200

10200共有3件物品

重量分别为30/80/10

价值分别为300/1200/200

背包最大载重量为100SampleOutput14000/1背包问题SampleInputSampleOutput160/1背包问题令f[i,j]表示考虑完前i项物品，并且当前背包承重不大于j的情况下能获得的最大价值f[i,j]=max(

f[i-1,j],//不选第i项物品

f[i-1,j–w[i]]+v[i])//选择第i项物品边界条件f[0,i]=0目标f[n,limit]0/1背包问题令f[i,j]表示考虑完前i项物品，并且当前背170/1背包问题我们注意到，f[i,j]仅与f[i-1,j]和

f[i-1,j-w[i]]有关，因此没必要保存二维数组令f[i]表示背包承重不大于i的情况下最大价值0/1背包问题我们注意到，f[i,j]仅与f[i-1,j]和180/1背包问题fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=limitdowntow[i]do

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);为什么循环倒序？0/1背包问题fillchar(f,sizeof(f),0)19完全背包问题共有N种物品，每种物品有一定的重量w[i]和一定的价值v[i]，每种物品有无限个。现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=10000完全背包问题共有N种物品，每种物品有一定的重量w[i]和一定20完全背包问题fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=w[i]tolimitdo

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);完全背包问题fillchar(f,sizeof(f),0);21多重背包问题共有N种物品，每种物品有一定的重量w[i]和一定的价值v[i]，每种物品有c[i]个。现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=10000多重背包问题共有N种物品，每种物品有一定的重量w[i]和一定22多重背包问题SampleInput3100

303002

8012001

102008共有3件物品

重量分别为30/80/10

价值分别为300/1200/200

数量分别为2/1/8

背包最大载重量为100SampleOutput1700方案：

1件物品1

7件物品3多重背包问题SampleInputSampleOutpu23多重背包问题想法1：把每件物品替换为c[i]件相同的物品，当做0/1背包处理。编号1234567891011W3030801010101010101010V3003001200200200200200200200200200这是原1号物品这是原2号物品这是原3号物品复杂度太高！多重背包问题想法1：把每件物品替换为c[i]件相同的物品，当24多重背包问题想法2：把每件物品按照二进制拆分1=12=1+13=1+24=1+2+15=1+2+26=1+2+37=1+2+48=1+2+4+19=1+2+4+210=1+2+4+3...15=1+2+4+816=1+2+4+8+117=1+2+4+8+2多重背包问题想法2：把每件物品按照二进制拆分25多重背包问题编号1234567W30308010204010V3003001200200400800200这是原1号物品这是原2号物品这是原3号物品多重背包问题编号1234567W3030801020401026最大伤害将AT值看做体积，将造成的伤害看做价值。若先不考虑释放最后一个魔法的冷却时间，这就是一个完全背包问题。做完完全背包后，枚举释放的最后一次魔法是什么和释放最后一次魔法时剩余AT是多少，判定是否能够释放成功，更新答案。最大伤害将AT值看做体积，将造成的伤害看做价值。27最大伤害样例1：

驱动魔法所需耗费AT为16，冷却魔法所耗费AT为5。做完背包后，f[21]=100，f[42]=200，f[63]=300，f[84]=400。枚举释放最后一次魔法剩余AT是多少，比如枚举到AT=84，84+16=100，所以最后一次魔法能够释放成功，最大伤害500。最大伤害样例1：

驱动魔法所需耗费AT为16，冷却魔法所耗费28最长公共子序列求两个字符串的最长公共子序列。最长公共子序列定义：

如果存在一个严格递增的下标序列b1,b2,b3,b4....bk,使得所有的Zi

=Xbi

那么Z是X的子序列(注意:子序列和子串不同,子串的下标必须连续,子序列则可以不连续,但要递增)。给定两个序列X,Y,如果Z既是X的子序列,也是Y的子序列,那么Z是X和Y的公共子序列。最长公共子序列求两个字符串的最长公共子序列。29最长公共子序列SampleInputABCDABA

BCABDASampleOutput5最长公共子序列SampleInputSampleOutp30最长公共子序列算法：动态规划f[i,j]表示第一个串的1~i与第二个串的1~j的最长公共子序列长度。f[i,j]=max{

f[i-1,j],

f[i,j-1],

f[i-1,j-1]+1(当Xi=Yj时)}最长公共子序列算法：动态规划31语音识别先去掉所有空格。用f[i,j]表示第一个串匹配到i，第二个串匹配到j的最小差异。f[i,j]=min{

f[i-1,j-1]+abs(s1[i]-s2[j]),

f[i-1,j]+5,

f[i,j-1]+5}语音识别先去掉所有空格。32石子合并N堆石子在操场上排成环状，每次可以合并相邻的两堆石子，耗费的体力值为两堆石子数量和，若想将所有石子合并到一堆，至少耗费多少体力？石子合并N堆石子在操场上排成环状，每次可以合并相邻的两堆石子33石子合并SampleInput4

4459SampleOutput43石子合并SampleInputSampleOutput34石子合并令f[i,j]表示合并完区间[i..j]耗费的最小体力f[i,j]=min{f[i,k]+f[k+1,j],i<=k<j}

+w[i,j]环的处理方法：可以将序列复制一份放到序列后，以样例为例，新序列为44594459，答案为f[1,4],f[2,5],f[3,6],f[4,7]中的最小值复杂度O(N^3)石子合并令f[i,j]表示合并完区间[i..j]耗费的最小体35石子合并四边形不等式在动态规划中，有一类常见的状态转移方程对于i<=i'<=j<=j'假如有w(i,j)+w(i',j')<=w(i',j)+w(i,j')，那么我们称函数w满足四边形不等式。石子合并四边形不等式36石子合并定理1：若w满足四边形不等式，则m也满足四边形不等式，即m(i,j)+m(i',j')<=m(i',j)+m(i,j')令s[i,j]表示f[i,j]取得最优值的决策定理2：若f满足四边形不等式，则s单调，即s[i,j-1]<=s[i,j]<=s[i+1,j]证明较复杂，略于是复杂度成功降到了O(N^2)石子合并定理1：若w满足四边形不等式，则m也满足四边形不等式37括号序列空序列是规则序列。如果S是规则序列，那么(S)和[S]也是规则序列。如果A和B都是规则序列，那么AB也是规则序列。现在给出一些由()[]构成的序列，请添加尽量少的括号，得到一个规则序列。括号序列空序列是规则序列。38括号序列SampleInput([(]SampleOutput()[()]括号序列SampleInputSampleOutput39括号序列情况1：S形如(S’)或[S’]

只需将S’变成规则序列即可S=([])S’=[]括号序列情况1：S形如(S’)或[S’]

只需将S’变成规则40括号序列情况2：S形如(S’或[S’

只需将S’变成规则序列后，添加)或]即可。S=([]S’=[]括号序列情况2：S形如(S’或[S’

只需将S’变成规则序列41括号序列情况3：S形如S’)或S’]

只需将S’变成规则序列后，添加(或(即可。S=()]S’=()括号序列情况3：S形如S’)或S’]

只需将S’变成规则序列42括号序列情况4：S可被拆分成两部分S1和S2，只需将S1和S2分别变成规则序列即可。S=()[]S1=()S2=[]括号序列情况4：S可被拆分成两部分S1和S2，只需将S1和S43括号序列f[i,j]表示将i..j变成规则序列至少要添加的括号数。f[i,j]=min{

f[i+1,j+1],//要求s[i]s[j]为()或[]

f[i+1,j]+1,//要求s[i]为(或[

f[i,j-1]+1,//要求s[j]为)或]

f[i,k]+f[k+1,j],i<=k<j}时间复杂度O(N^3)括号序列f[i,j]表示将i..j变成规则序列至少要添加的括44决斗N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？决斗N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（45决斗SampleInput3

010

001

1001胜2

2胜3

3胜1SampleOutput123若23先决斗，则1胜

若13先决斗，则2胜

若12先决斗，则3胜决斗SampleInputSampleOutput46决斗把环复制一份，接到环后面，这样编号为x的人能胜出的充要条件是他能与自己

“相遇”。123456

1对应4，2对应5，3对应6

由于2可以胜3，因此2将3淘汰后，2和4会相遇，又因为1可以胜2，因此1将2淘汰后，1和4会相遇，所以1可能赢得这场决斗。决斗把环复制一份，接到环后面，这样编号为x的人能胜出的充要条47决斗设meet[i,j]表示i和j是否能够相遇。若存在i<k<j满足meet[i,k]&&meet[k,j]&&(defeat[i,k]||defeat[j,k])，则meet[i,j]=true，否则meet[i,j]=false决斗设meet[i,j]表示i和j是否能够相遇。48决斗fori:=1ton+n-1domeet[i,i+1]=true;forl:=3ton+ndofori:=1ton+n-l+1dobegin

j:=i+l-1;

fork:=i+1toj-1do

ifmeet[i,k]andmeet[k,j]and

(defeat[i,k]ordefeat[j,k])then

meet[i,j]=true;end;fori:=1tondoifmeet[i,i+n]thenwriteln(i);决斗fori:=1ton+n-1domeet[i,49三取方格数N*N的方格，每个方格有一定的权值，三个人从左上角向右下角走，只能向下或向右，求最大路径和，走过多次的方格权值只计算一次。三取方格数N*N的方格，每个方格有一定的权值，三个人从左上角50三取方格数SampleInput4

1234

2134

1234

1324SampleOutput39三取方格数SampleInputSampleOutput51三取方格数由于走过多次的方格权值只算一次，因此贪心不可取。考虑一个人的情况

f[r,c]=max{f[r’,c’]}+v[r,c]

其中r’c’可以到达rc由此可以推出三个人的方程f[r1,c1,r2,c2,r3,c3]=

max(f[r1’,c1’,r2’,c2’,r3’,c3’])

+value，这里value视情况而定三取方格数由于走过多次的方格权值只算一次，因此贪心不可取。52三取方格数时间复杂度为O(N^6)，太高！走了相同步数的人，r+c是相同的。因此我们可以按斜线划分状态三取方格数时间复杂度为O(N^6)，太高！53三取方格数f[s,r1,r2,r3]表示，三个人的x坐标与y坐标和为s，并且纵坐标分别为r1，r2，r3时，最大的路径权值和。f[s,r1,r2,r3]=

max{f[s-1,r1’,r2’,r3’]}+value

其中f[s-1,r1’,r2’,r3’]可以通过一步到达f[s,r1,r2,r3]，value视情况而定时间复杂度O(N^4)三取方格数f[s,r1,r2,r3]表示，三个人的x坐标与y54选课有N门选修课，每门课程有一门直接的先修课，课程1没有先修课。每门选修课有一定的学分，现在要求你选择M门选修课，使学分总和最大。选课有N门选修课，每门课程有一门直接的先修课，课程1没有先修55选课SampleInput43

50

91

11

103SampleOutput16

方案：

选择课程1、3、4。选课SampleInputSampleOutput56选课多叉树转二叉树左孩子右兄弟12341234选课多叉树转二叉树1234123457选课用f[i,j]表示以i为根的子树中，选择j门课程能够获得的最大学分数。f[i,j]=max{

f[left[i],k]+f[right[i],j-k-1]+v[i],

f[right[i],j]}选课用f[i,j]表示以i为根的子树中，选择j门课程能够获得58贪吃的九头龙一棵有边权的树，要求你把每个节点染成1~M中的某种颜色，要求根节点必须为颜色1，颜色1的节点数量恰好为K，若某条边两端节点颜色相同，则这条边的权值计入答案。问最小权值和是多少？贪吃的九头龙一棵有边权的树，要求你把每个节点染成1~M中的某59贪吃的九头龙颜色虽说有M种，但其实可以分为两类：颜色1和非颜色1。若M=2，则边两端均为或均不为颜色1需要计入答案，若M>2，则边两端均为颜色1需要计入答案，均不为颜色1的边可以通过交叉染色不计入答案。贪吃的九头龙颜色虽说有M种，但其实可以分为两类：颜色1和非颜60贪吃的九头龙多叉转二叉左孩子右兄弟略过贪吃的九头龙多叉转二叉61贪吃的九头龙用f[i,j,k]表示以i为根的子树中，将j个节点染成颜色1，并且i的父亲颜色为k（k=1表示染成颜色1，k=0表示染成除颜色1外的其他颜色）最小权值和。贪吃的九头龙用f[i,j,k]表示以i为根的子树中，将j个节62贪吃的九头龙

贪吃的九头龙

63谢谢大家QQ：892493591E-mail：zbwmqlw@blog：/zbwmqlw欢迎骚扰谢谢大家QQ：89249359164动态规划例题讲解山东师大附中魏铭动态规划例题讲解山东师大附中65Preview本节课主要通过几道例题，总揽NOIp中较常见的动态规划模型，不会过多涉及优化内容。万丈高楼平地起Preview本节课主要通过几道例题，总揽NOIp中较常见的66Preview最长上升子序列内存碎片背包问题最长公共子序列石子合并括号序列决斗三取方格数选课贪吃的九头龙Preview最长上升子序列括号序列67最长上升子序列给出一个数列{a1,a2,...,an}，要求你选出尽量多的元素，使这些元素按其相对位置单调递增。SampleOutput4SampleInput9

5

8

9

2

3

1

7

4

6最长上升子序列给出一个数列{a1,a2,...,an}，要求68最长上升子序列算法：动态规划令f[i]表示以ai为结尾的最长上升子序列的长度转移方程：

f[i]=max(f[j],1<=j<i,a[j]<a[i])+1时间复杂度：O(N^2)最长上升子序列算法：动态规划69最长上升子序列换一种状态表示方法令f[i]表示长度为i的上升子序列的结尾数字最小是多少初始f[0]=-inf,f[i]=inf（inf为无穷大，可取值为大于任意ai绝对值的一个数字）最长上升子序列换一种状态表示方法70最长上升子序列F[0]F[1]F[2]F[3]F[4]初始-infinfinfinfinf插入a1后-inf5infinfinf插入a2后-inf58infinf插入a3后-inf589inf插入a4后-inf289inf插入a5后-inf239inf插入a6后-inf139inf插入a7后-inf137inf插入a8后-inf134inf插入a9后-inf1346SampleInput5

8

9

2

3

1

7

4

6最长上升子序列F[0]F[1]F[2]F[3]F[4]初始-71最长上升子序列f[]是单调递增的，因为如果有i<j且f[i]>=f[j]，那么f[i]必定可以被f[j]的方案所更新。每处理到一个ai，我们要找到一个k满足

f[k–1]<ai且f[k]>=ai，并用ai更新f[k]，最终max(k|f[k]!=inf)就是答案。可以通过二分查找将时间复杂度降至

O(NlogN)最长上升子序列f[]是单调递增的，因为如果有i<j且f[i]72选人将所有人按照智商排序，以情商为关键字，求最长上升子序列的长度即可。选人将所有人按照智商排序，以情商为关键字，求最长上升子序列的73内存碎片N个内存申请请求，申请长度为L[i]的内存块c[i]次。当程序申请长度为L的内存时，也可以给它分配一块长度为L’（L’>L）的更大的内存块。内存长度种类不超过K。求最少需要的内存。内存碎片N个内存申请请求，申请长度为L[i]的内存块c[i]74内存碎片SampleInput32

101

111

2013个内存申请最多2种长度SampleOutput42

方案：

两个11，一个20内存碎片SampleInputSampleOutput75内存碎片算法：动态规划先将所有L[i]排序。11234467822244

66

881133

666882

33377778这一行是内存申请的长度这三行是内存分配的可能长度内存碎片算法：动态规划这一行是内存申请的长度这三行是内存分配76内存碎片一种内存长度覆盖的区间必定是连续的，并且该内存长度等于覆盖区间最后一个内存申请操作的长度。令f[i,j]表示考虑完前i个内存申请操作，并且已经使用完j种内存长度的最少需要的内存。内存碎片一种内存长度覆盖的区间必定是连续的，并且该内存长度等77内存碎片f[i,j]=min{

f[k,j-1]+

(c[k+1]+c[k+2]+...+c[i])*L[i],0<=k<i}预处理sc[i]=c[1]+c[2]+...+c[i]f[i,j]=min{

f[k,j-1]+(sc[i]-sc[k])*L[i],0<=k<i)}时间复杂度O(N^2*K)内存碎片f[i,j]=min{

f[k,j-1]+

(c[780/1背包问题共有N件物品，每件物品有一定的重量w[i]和一定的价值v[i]，现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=100000/1背包问题共有N件物品，每件物品有一定的重量w[i]和一790/1背包问题SampleInput3100

30300

801200

10200共有3件物品

重量分别为30/80/10

价值分别为300/1200/200

背包最大载重量为100SampleOutput14000/1背包问题SampleInputSampleOutput800/1背包问题令f[i,j]表示考虑完前i项物品，并且当前背包承重不大于j的情况下能获得的最大价值f[i,j]=max(

f[i-1,j],//不选第i项物品

f[i-1,j–w[i]]+v[i])//选择第i项物品边界条件f[0,i]=0目标f[n,limit]0/1背包问题令f[i,j]表示考虑完前i项物品，并且当前背810/1背包问题我们注意到，f[i,j]仅与f[i-1,j]和

f[i-1,j-w[i]]有关，因此没必要保存二维数组令f[i]表示背包承重不大于i的情况下最大价值0/1背包问题我们注意到，f[i,j]仅与f[i-1,j]和820/1背包问题fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=limitdowntow[i]do

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);为什么循环倒序？0/1背包问题fillchar(f,sizeof(f),0)83完全背包问题共有N种物品，每种物品有一定的重量w[i]和一定的价值v[i]，每种物品有无限个。现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=10000完全背包问题共有N种物品，每种物品有一定的重量w[i]和一定84完全背包问题fillchar(f,sizeof(f),0);

fori:=1tondo

forj:=w[i]tolimitdo

f[j]=max(f[j],f[j-w[i]]+v[i]);

writeln(f[limit]);完全背包问题fillchar(f,sizeof(f),0);85多重背包问题共有N种物品，每种物品有一定的重量w[i]和一定的价值v[i]，每种物品有c[i]个。现在我们有一个最大载重量limit的包，问放入哪些物品能使得总价值最高？w[i]和v[i]均为整数，N<=100，limit<=10000多重背包问题共有N种物品，每种物品有一定的重量w[i]和一定86多重背包问题SampleInput3100

303002

8012001

102008共有3件物品

重量分别为30/80/10

价值分别为300/1200/200

数量分别为2/1/8

背包最大载重量为100SampleOutput1700方案：

1件物品1

7件物品3多重背包问题SampleInputSampleOutpu87多重背包问题想法1：把每件物品替换为c[i]件相同的物品，当做0/1背包处理。编号1234567891011W3030801010101010101010V3003001200200200200200200200200200这是原1号物品这是原2号物品这是原3号物品复杂度太高！多重背包问题想法1：把每件物品替换为c[i]件相同的物品，当88多重背包问题想法2：把每件物品按照二进制拆分1=12=1+13=1+24=1+2+15=1+2+26=1+2+37=1+2+48=1+2+4+19=1+2+4+210=1+2+4+3...15=1+2+4+816=1+2+4+8+117=1+2+4+8+2多重背包问题想法2：把每件物品按照二进制拆分89多重背包问题编号1234567W30308010204010V3003001200200400800200这是原1号物品这是原2号物品这是原3号物品多重背包问题编号1234567W3030801020401090最大伤害将AT值看做体积，将造成的伤害看做价值。若先不考虑释放最后一个魔法的冷却时间，这就是一个完全背包问题。做完完全背包后，枚举释放的最后一次魔法是什么和释放最后一次魔法时剩余AT是多少，判定是否能够释放成功，更新答案。最大伤害将AT值看做体积，将造成的伤害看做价值。91最大伤害样例1：

驱动魔法所需耗费AT为16，冷却魔法所耗费AT为5。做完背包后，f[21]=100，f[42]=200，f[63]=300，f[84]=400。枚举释放最后一次魔法剩余AT是多少，比如枚举到AT=84，84+16=100，所以最后一次魔法能够释放成功，最大伤害500。最大伤害样例1：

驱动魔法所需耗费AT为16，冷却魔法所耗费92最长公共子序列求两个字符串的最长公共子序列。最长公共子序列定义：

如果存在一个严格递增的下标序列b1,b2,b3,b4....bk,使得所有的Zi

=Xbi

那么Z是X的子序列(注意:子序列和子串不同,子串的下标必须连续,子序列则可以不连续,但要递增)。给定两个序列X,Y,如果Z既是X的子序列,也是Y的子序列,那么Z是X和Y的公共子序列。最长公共子序列求两个字符串的最长公共子序列。93最长公共子序列SampleInputABCDABA

BCABDASampleOutput5最长公共子序列SampleInputSampleOutp94最长公共子序列算法：动态规划f[i,j]表示第一个串的1~i与第二个串的1~j的最长公共子序列长度。f[i,j]=max{

f[i-1,j],

f[i,j-1],

f[i-1,j-1]+1(当Xi=Yj时)}最长公共子序列算法：动态规划95语音识别先去掉所有空格。用f[i,j]表示第一个串匹配到i，第二个串匹配到j的最小差异。f[i,j]=min{

f[i-1,j-1]+abs(s1[i]-s2[j]),

f[i-1,j]+5,

f[i,j-1]+5}语音识别先去掉所有空格。96石子合并N堆石子在操场上排成环状，每次可以合并相邻的两堆石子，耗费的体力值为两堆石子数量和，若想将所有石子合并到一堆，至少耗费多少体力？石子合并N堆石子在操场上排成环状，每次可以合并相邻的两堆石子97石子合并SampleInput4

4459SampleOutput43石子合并SampleInputSampleOutput98石子合并令f[i,j]表示合并完区间[i..j]耗费的最小体力f[i,j]=min{f[i,k]+f[k+1,j],i<=k<j}

+w[i,j]环的处理方法：可以将序列复制一份放到序列后，以样例为例，新序列为44594459，答案为f[1,4],f[2,5],f[3,6],f[4,7]中的最小值复杂度O(N^3)石子合并令f[i,j]表示合并完区间[i..j]耗费的最小体99石子合并四边形不等式在动态规划中，有一类常见的状态转移方程对于i<=i'<=j<=j'假如有w(i,j)+w(i',j')<=w(i',j)+w(i,j')，那么我们称函数w满足四边形不等式。石子合并四边形不等式100石子合并定理1：若w满足四边形不等式，则m也满足四边形不等式，即m(i,j)+m(i',j')<=m(i',j)+m(i,j')令s[i,j]表示f[i,j]取得最优值的决策定理2：若f满足四边形不等式，则s单调，即s[i,j-1]<=s[i,j]<=s[i+1,j]证明较复杂，略于是复杂度成功降到了O(N^2)石子合并定理1：若w满足四边形不等式，则m也满足四边形不等式101括号序列空序列是规则序列。如果S是规则序列，那么(S)和[S]也是规则序列。如果A和B都是规则序列，那么AB也是规则序列。现在给出一些由()[]构成的序列，请添加尽量少的括号，得到一个规则序列。括号序列空序列是规则序列。102括号序列SampleInput([(]SampleOutput()[()]括号序列SampleInputSampleOutput103括号序列情况1：S形如(S’)或[S’]

只需将S’变成规则序列即可S=([])S’=[]括号序列情况1：S形如(S’)或[S’]

只需将S’变成规则104括号序列情况2：S形如(S’或[S’

只需将S’变成规则序列后，添加)或]即可。S=([]S’=[]括号序列情况2：S形如(S’或[S’

只需将S’变成规则序列105括号序列情况3：S形如S’)或S’]

只需将S’变成规则序列后，添加(或(即可。S=()]S’=()括号序列情况3：S形如S’)或S’]

只需将S’变成规则序列106括号序列情况4：S可被拆分成两部分S1和S2，只需将S1和S2分别变成规则序列即可。S=()[]S1=()S2=[]括号序列情况4：S可被拆分成两部分S1和S2，只需将S1和S107括号序列f[i,j]表示将i..j变成规则序列至少要添加的括号数。f[i,j]=min{

f[i+1,j+1],//要求s[i]s[j]为()或[]

f[i+1,j]+1,//要求s[i]为(或[

f[i,j-1]+1,//要求s[j]为)或]

f[i,k]+f[k+1,j],i<=k<j}时间复杂度O(N^3)括号序列f[i,j]表示将i..j变成规则序列至少要添加的括108决斗N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？决斗N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（109决斗SampleInput3

010

001

1001胜2

2胜3

3胜1SampleOutput123若23先决斗，则1胜

若13先决斗，则2胜

若12先决斗，则3胜决斗SampleInputSampleOutput110决斗把环复制一份，接到环后面，这样编号为x的人能胜出的充要条件是他能与自己

“相遇”。123456

1对应4，2对应5，3对应6

由于2可以胜3，因此2将3淘汰后，2和4会相遇，又因为1可以胜2，因此1将2淘汰后，1和4会相遇，所以1可能赢得这场决斗。决斗把环复制一份，接到环后面，这样编号为x的人能胜出的充要条111决斗设meet[i,j]表示i和j是否能够相遇。若存在i<k<j满足meet[i,k]&&meet[k,j]&&(defeat[i,k]||defeat[j,k])，则meet[i,j]=true，否则meet[i,j]=false决斗设meet[i,j]表示i和j是否能够相遇。112决斗fori:=1ton+n-1domeet[i,i+1]=true;forl:=3ton+ndofori:=1ton+n-l+1dobegin

j:=i+l-1;

fork:=i+1toj-1do

ifmeet[i,k]andmeet[k,j]and