基本原理
1、多阶段最优化决策：即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。

 

带权有向的多段图 概念
⑴状态（state）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。
⑵阶段（stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。
⑶决策（decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。
⑷状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设
    fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价
        fk+1(i)=min{xk(j)+u(i,j)} 基本原理
最优性原理
  
  作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。 无后效性原则
  
  给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
机器分配
总公司拥有高效生产设备m台，准备分给下属的n个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这m台设备才能使国家得到的盈利最大？求出最大盈利值。其中m<=15，n<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数m。
数据文件格式为：第一行保存两个数，第一个数是设备台数m，第二个数是分公司数n。接下来是一个m*n的矩阵，表明了第i个公司分配j台机器的盈利。
分析
用机器数来做状态，数组f[i，j]表示前i个公司分配j台机器的最大盈利。则状态转移方程为:
f[i，j]=max{f[i-1，k] + value[i，j-k]} (1<=i<=n,1<=j<=m,0<=k<=j )
初始值: f(0,0)=0
时间复杂度o(n*m2)
最长不下降序列
设有整数序列b1,b2,b3,…,bm，若存在下标i1<i2<i3< …<in，且bi1<bi2<bi3< …<bin，则称 b1,b2,b3,…,bm中有长度为n的不下降序列bi1 , bi2 ,bi3 ,…,bin 。
求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列
输入：整数序列。
输出：最大长度n和所有长度为n的序列个数。
分析
（1）设f(i)为前i个数中的最大不下降序列长度 , 则
f(i)=max{f(j)+1}   (1<=j<i<=m, bj<bi)
边界为f(1)=1
(2)设t(i)为前i个数中最长不下降序列的个数,则
t(i)=∑t(j) (1<=j<i<=m , bj<bi, f(i)=f(j)-1)
初始为t(i)=1
当f(i)=n时，将t(i)累加
举例：
        1  2  3  4  6  5  8  10 9
       f:   1  2  3  4  5  5  6  7   7
       t:   1  1  1  1  1  1  2  2   2
答案：f=7时，边界为∑t=4
进一步
改进算法
上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：
对原序列按b从小到大（当bi=bj时按f从大到小）排序，增设order(i)记录新序列中的i个数在原序列中的位置。可见，
求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且order(j+1)<order(i)时，便不累加t(j)。这样就避免了重复。
 上述算法的时间复杂度为o(n2)
凸多边形三角划分
给定一个具有n（n<50）个顶点（从1到n编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成n-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？
输入文件：第一行 顶点数n
          第二行 n个顶点（从1到n）的权值
输出格式：最小的和的值
          各三角形组成的方式
输入示例：5
122  123  245  231
输出示例：the  minimum  is ：12214884
          the  formation  of 3 triangle:
          3 4 5, 1 5 3, 1 2 3 分析
设f[i,j]（i<j）表示从顶点i到顶点j的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：
f[i,j]=min{f[i,k]+f[k,j]+s[i]*s[j]*s[k]}     (0<i<k<j<=n)
初始条件:f[1，2]=0
目标状态:f[1,n]
但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算
系统可靠性
分析
例：输入：2  20                    3  0 .6  0.65  0.7  0.75  0.8  0.85  0.9
                    5  0.7  0.75  0.8  0.8  0.9  0.95
             输出：0.6375
设f[i,money]表示将money的资金用到前i项备用件中去的最大可靠性，则有
   f[i,money] = max{f[i-1 ,money–k*cost[i] ]*p[i,k] }
       (0<=i<=n,0<=k<= money div cost(i) )
初始： f[0,0]=0
目标： f[n,c] 快餐问题
peter最近在r市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由a个汉堡，b个薯条和c个饮料组成。价格便宜。为了提高产量，peter从著名的麦当劳公司引进了n条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。
输入:第一行为三个不超过100的正整数a、b、c中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为n(0<=0<=10)，第四行为n个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。
输出:每天套餐的最大产量。
分析
本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。
状态表示：用p[i,j,k]表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。
用r[i,j,k]表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。
态转移方程 ： p[i,j,k] = max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}
  ( 0<=j1<=j<=100,0<=k1<=k<=100,
    且(j-j1)*p1+(k-k1)*p2<=t[i]---第i条生产线的生产时间 )
r[i,j-j1,k-k1]=(t[i]-(j-j1)*p1+(k-k1)*p2) div p3 ;
此算法的时间复杂度为o(n*1004),
优化
在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由a,b,c计算，即min｛100 div a，100 div b，100 div c｝），接着，用贪心法计算出这n条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：
s1：读入数据。
s2：贪心求上限并计算出一可行解，判断是否需进行下一步。
s3：动态规划求解。
s4：输出。
其他优化方法
1.存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。
2.减少循环次数：在计算每一阶段状态过程中无疑要用到4重循环，我们可以这样修改每一重循环的起始值和终数，其中q1,q2为a，b上限值。
 原起始值                      改进后的起始值
for i:=1 to n do                     for i:=1 to n do
for j:=0 to tot[i] div p1 do         for j:=0 to min(q1,tot[i] div p1) do
for k:=0 to (tot[i]-p1*j) div p2 do  for k:=0 to min(q2,(tot[i]-p1*j)div p2) do
for j1:=0 to j do                    for j1 := max(0,j-t[i] div p1) to
                                                  min(j,tot[i-1] div p1) do
     for k1 := 0 to k do             for k1:=max(0,k-(t[i]-(j-j1)*p1) div p2)
                                             to min(k,(tot[i-1]-p1*j1)div p2) do
石子合并
在一园形操场四周摆放n堆石子(n≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数n及每堆石子数(≤20),  
(1)选择一种合并石子的方案,使得做n-1次合并,得分的总和最少
(2) 选择一种合并石子的方案,使得做n-1次合并,得分的总和最大
输入数据:
 第一行为石子堆数n;
 第二行为每堆石子数,每两个数之间用一空格分隔.
输出数据 :
 从第1至第n行为得分最小的合并方案. 第n+1行为空行.从n+2到2n+1行是得分最大的合并方案.
示例
贪心法
动态规划
用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，
max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：
max[i,j] = max(max[i, k] + max[i + k, j – k] + data[i,k] + data[i+k, j–k]) (2<=k<=j)
max[i,1] = 0
同样的，我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：
min[i,j] = min(min[i, k] + min[i + k, j – k] + data[i,k] + data[i+k, j– k]) (0<=k<=j)
min[i,0] = 0
这样，我们完美地解决了这道题。时间复杂度也是o(n2)。
积木游戏
一种积木游戏，游戏者有n块编号依次为1，2，…，n的长方体积木。第i块积木通过同一顶点三条边的长度分别为ai,bi,ci（i=1,2,…,n），1 从n块积木中选出若干块，并将他们摞成m（1<= m <= n）根柱子，编号依次为1,2,…,m，要求第k根柱子的任意一块积木的编号都必须大于第k-1根柱子任意一块积木的编号（2<=k<=m）。
2 对于每一根柱子，一定要满足下面三个条件：
除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触；
对于任意两块上下表面相接触的积木，若m,n是下面一块积木接触面的两条边（m>=n），x,y是上面一块积木接触面的两条边（x>=y），则一定满足m.>=x和n>=y；
下面的积木的编号要小于上面的积木的编号。
请你编一程序，寻找一种游戏方案，使得所有能摞成的m根柱子的高度之和最大。
积木游戏
输入数据：
文件的第一行是两个正整数n和m（1<= m <= n <=100）,分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来的n行是编号从1到n个积木的尺寸，每行有三个1至500之间的整数，分别表示该积木三条边的长度。同一行相邻两个数之间用一个空格符隔开。
输出数据：
文件只有一行，是一个整数，表示所求得的游戏方案中m根柱子的高度之和 分析
设
（1） f[i,j,k]表示以第i块积木的第k面为第j根柱子的顶面的最优方案的高度总和；
（2）block[i,k] 记录每个积木的三条边信息（block[i,4]:=block[i,1]; block[i,5]:=block[i,2]）。其中block[i,j+2]表示当把第i块积木的第j面朝上时所对应的高，即所增加的高度；
（3）can[i,k,p,kc]表示第i块积木以其第k面朝上，第p块积木以第kc面朝上时，能否将积木i放在积木p的上面。1表示能，0表示不能。对于f[i,j,k], 有两种可能：
      1. 除去第i块积木，第j根柱子的最上面的积木为编号为p的，若第p块积木以第kc面朝上，必须保证当第i块积木以k面朝上时能够被放在上面，即can[i,k,p,kc]=1；
      2. 第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为第p块积木，则此时第p块积木可以以任意一面朝上。则有：
动态规划
边界条件：
f[1,1,1]:=block[1,1,3]; f[1,1,2]:=block[1,1,4]; f[1,1,3]:=block[1,1,5];
f[i,0,k]:=0; (1<= i <= n, 1<= k <= 3);
时间复杂度为o(n^2*m)
免费馅饼
serkoi最新推出了一种叫做“免费馅饼”的游戏。
游戏在一个舞台上进行。舞台的宽度为w格，天幕的高度为h格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。
免费馅饼
输入数据：输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度w（1~99之间的奇数）和高度h（1 ~ 100之间的整数）。
接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0 ~ 1000秒），水平位置、下落速度（1 ~ 100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。
输出数据：输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。
分析
我们将问题中的馅饼信息用一个表格存储。表格的第i行第j列表示的是游戏者在第i秒到达第j列所能取得的分值。那么问题便变成了一个类似数字三角形的问题：从表格的第一行开始往下走，每次只能向左或右移动一格或两格，或不移动走到下一行。怎样走才能得到最大的分值。
因此，我们很容易想到用动态规划求解。
f[i,j]表示游戏进行到第i秒，这时游戏者站在第j列时所能得到的最大分值。那么动态转移方程为：
      f[i,j] = max { f[i-1,k] } + 馅饼的分值 
      ( j-2<=k<=j+2 )
商店购物
 某商店中每种商品都有一个价格。例如，一朵花的价格是2 icu(icu 是信息学竞赛的货币的单位）;一个花瓶的价格是5 icu。为了吸引更多的顾客，商店提供了特殊优惠价。
    特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 icu ;2个花瓶加1朵花是10 icu不是12 icu。
    编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 icu因为:
         1朵花加2个花瓶: 优惠价:10  icu
         2朵花            正常价: 4  icu 商店购物
输入数据
  第一个文件input．txt的格式为:第一行是一个数字b（0≤b≤5），表示所购商品种类数。下面共b行，每行中含3个数c，k，p。c 代表商品的编码（每种商品有一个唯一的编码），1≤c≤999。k代表该种商品购买总数，1≤k≤5。p 是该种商品的正常单价（每件商品的价格），1≤p≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件offer．txt的格式为:第一行是一个数字s（0≤s≤99），表示共有s种优惠。下面共s行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（c，k），其中c代表商品编码，1≤c≤9 99。k代表该种商品在此组合中的数量，1≤k≤5。本行最后一个数字p（1≤ p≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据
  在输出文件output．txt中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
分析
由于动态规划要满足无后效性和最优化原理，所以我们来分析此题是否满足以上两点。首先确定状态，商品不超过5种，而每种采购的数量又不超过5，那么用一个五元组来表示第i种商品买ai的最小费用。
f（a1，a2，a3，a4，a5）       （1）
考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。于是如果我们能够使用第i条商品组合的话，状态就b变为了：
f（a1-si1，a2-si2，a3-si3，a4-si4，a5-si5）     （2）
这样的话，状态1的费用为状态2的费用加上si的费用，而状态2的费用必须最低（很显然，用反证法即可），同时，我们也不管状态2是如何来的（因为每一个优惠商品组合的使用是没有限制的），所以本题既满足无后效性，又符合最优化原理，同时还有大量重叠子问题产生，动态规划解决此题是最好不过了。
状态转移方程
f [a, b, c, d, e] =
          min{f[a-si1,b-si2,c-si3,d-si4,e-si5]+salecost[si]}
   (0<=i<=s, 0<=a, b, c, d, e<=5)
初始条件为：
 f [a, b, c, d, e] =
     cost[1]*a+cost[2]*b+cost[3]*c+cost[4]*d+cost[5]*e 添括号问题
有一个由数字1，2，... ，9组成的数字串（长度不超过200），问如何将m(m<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。
注意：
加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。
m保证小于数字串的长度。
例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。
[输入格式］
从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。
[输出格式］
在屏幕上输出所求得的最小和的精确值。
分析
考虑到数据的规模超过了长整型,我们注意在解题过程中采用高精度算法.
规划方程:
f[i,j] = min { f[i-1,k] + num[k+1,j] } (i-1<=k<=j-1)
边界值:f[0,i] := num[1,i] ;
f[i，j]表示前j个数字中添上i个加号后得到的最小值。
num[i，j]表示数字串第i位到第j位的数
上述问题的每一步，都只与上一步有关。因此可以采用滚动数组
程序的时间效率约为 20 * 200 * 200
最长前缀
一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元（字符串）的序列。对于给定的基元集合p，如果可以从中选出n个基元p1，p2，p3，...,pn，将它们各自对应的字符串依次连接后得到一个字符串s，称s可以由基元集合p构成。在从p中挑选基元时，一个基元可以使用多次，也可不用。例如，序列 ababacabaab 可以由基元集合{a，ab，ba，ca，bbc} 构成。
字符串的前k个字符为该字符串的前缀，其长度为k。请写一个程序，对于输入的基元集合p和字符串t，求出一个可以由基元集合p构成的字符串t的前缀，要求该前缀的长度尽可能长，输出其长度。 最长前缀
输入数据：有两个输入文件 input.txt，data.txt
 input.txt 的第一行是基元集合p中的基元数目n（1<=n<=100）,随后有2n行，每两行描述一个基元，第一行为该基元的长度l（1<=l<=20）。随后一行是一个长度为l的大写英文字符串，表示该基元。每个基元互不相同。
 data.txt 描述要处理的字符串t，每一行行首有一个大写字母，最后一行是一个字符‘.’,表示字符串结束。t的长度最小为1，最大不超过500000。
输出数据：output.txt。只有一行，一个数字，表示可以由p构成的t的最长前缀的长度。
分析
本题可以简述为: 从一个集合里选出若干个基元,使其组成字符串t的前缀,求最长前缀的长度.
对于t的每个字符，其状态可分为两种：
在此之前的所有字符（包括本身）可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元组成)
用fi表示第i个字符的状态，finda,b表示由第a至b位的字符组成的子串是否存在于集合中，则，
  fi = fi or (fk and findk+1,j)  (0<=k<=i-1)
初始条件:
    if i=0 then fi:= true else fi:= false
分析
由于t的长度最大达500000，无法存放所有状态，但集合里基元长度不超过20，因此可只保留当前20位字符与状态。当20位字符都不可以匹配时，停止运算，最后一个状态为true的字符的位置，即为所求。
为了便于操作，可用字符串表示状态，‘0’表false、‘1’表true.
为了便于查找，可将基元按长度存储。
形如：s[i,j]，表示长度为 i的第 j个基元。
亦可采用树的结构存储基元，构造一种多叉树（最多26叉），查找时顺着相应字母，定位到相应分支。这样速度要快些，但程序更复杂。大家可以比较一下。
按树结构算，时间复杂度为o(500000*l*l),勉强可以承受。
多边形
多角形是一个单人玩的游戏，开始时有一个n个顶点的多边形。如图，这里n=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到n。
    第一步，一条边被拿走；随后各步包括如下：
    选择一条边e和连接着e的两个顶点v1和 v2；
    得到一个新的顶点，标记为v1与v2通过边e上的运算符运算的结果。
    最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。
样例
分析
分析
我们在这条“线”当中继续删边，并且每次删边都使被删边两旁的点按边上的操作符合并，图五。这样进行了n-1次删边操作后，“线” 变成了一个点。我们的目的，就是安排删边的顺序，使最后的点上的数尽可能的大。
拿到题目之后，我们马上可以想到用枚举法——枚举删边的先后顺序。但边数最大可以达到50，枚举的复杂将会有50！。因此枚举算法马上被排除了。
对最优化问题的求解，我们往往可以使用动态规划来解决。这道题是不是可以使用动态规划呢？
我们先对题目进行一些变化——原题中顶点上的数可以为负数，现在我们规定这个数一定大于等于0；原题中边可以为乘号，现在我们规定只能为加号。
题意改变后，我们想到了什么？对！“石子合并”。
动态规划
我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值
用f(i,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，那么： 进一步分析
现在我们来考虑加入乘号后的情况。
由于所有的顶点上的数都为非负数，因此即使有了乘法，函数f的无后效性并不被破坏。我们可以在前一方程的基础上进行改进：（opr(i)表示第i条边上的操作符） 进一步分析
最后，我们允许顶点上出现负数。以前的方程还适不适用呢？  
这个例子的最优解应该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（（-10）*3+2）*（-5）=140。为什么？
我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。 
最终？
我们引入函数fmin和fmax来解决这个问题。fmax(i,j) 表示从j开始，进行i次删边操作所能得到的最大值，fmin(i,j) 表示从j开始，进行i次删边操作所能得到的最小值 。
完美解决
接下来讨论actmin(x1,y1,x2,y2)的构造： 当opr(x2-1)=+时，actmin=fmin(x1,y1)+fmin(x2,y2)
opr(x2-1)=*时，
 actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2)) 到此为止，整个问题圆满解决了。算法的空间复杂度为n2，算法时间复杂度为n4（先要枚举每一条边，然后再用复杂度为n3的动态规划解决）。 选课
大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。
每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。
选课
下面举例说明
上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。
学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
选课
 输入
    输入文件的第一行包括两个正整数m、n（中间用一个空格隔开）其中m表示待选课程总数（1≤m≤1000)，n表示学生可以选的课程总数（1≤n≤m)。
    以下m行每行代表一门课，课号依次为1，2……m。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
输出
    输出文件第一行只有一个数，即实际所选课程的学分总数。以下n行每行有一个数，表示学生所选课程的课号。 样例分析
分析
们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？
我们用函数f(i,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：
可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。 改造树
动态规划
1<=i<=m,1<=j<=n,0<=k<j
这个方程的时间复杂度最大为n3，十分优秀了。
在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解
hpc (winter camp 2001) 输入文件hpc.in
5 5
3
15 10   6 4
70 100 7 2
30 70   1 6
输出文件hpc.out
     93
分析p=1的情况
a个a类任务，b个b类任务，分两种情况讨论：
1.最后处理任务a                  2.最后处理任务b
p=1时，状态转移方程
设：
ga(a, b)表示处理a个a类任务，b个b类任务，
       且最后处理的是a类任务所需的最短时间。
gb(a, b)表示处理a个a类任务，b个b类任务，
      且最后处理的是b类任务所需的最短时间。
根据上面的讨论，可以得到：
ga(a, b) = min(1≤x≤a){gb(a – x, b) + kax2} + ta
gb(a, b) = min(1≤x≤b){ga(a, b – x) + kbx2} + tb 设：
 g(a, b)表示处理a个a类任务，b个b类任务所需的最短时间。这个问题可以分解为最后处理任务a或最后处理任务b两种情况。
     g(a, b) = min{ga(a, b), gb(a, b)}
p > 1
p>1的情况：
第一个节点负责了i个任务a和j个任务b，则
剩下的a – i个任务a和b – j个任务b都必须由后p – 1个节点完成。
设f(p, a, b)表示在后p个节点上处理a个a类任务，b个b类任务所需的最少时间。有：
   f(p, a, b) = min(0≤i≤a, 0≤j≤b){max{g(i, j), f(p – 1, a – i, b – j)}}
总结：
由于计算f(p)时，只需用到f(p – 1)的结果，故可以使用滚动数组。这样，计算过程中，只需保存ga, gb, g, f(p – 1), f(p)这5个大小为n2的数组，故空间复杂度是o(n2)。
计算数组g的复杂度为o(n3)，一共有p个节点，故时间复杂度是o(pn3)。计算数组f的复杂度为o(pn4)。所以，总的时间复杂度为o(pn4)。
在这个例子中，我们用f来表示目标问题。在求f之前，先要求出g，而在求g的时候，也采用了动态规划。我们称之为多次动态规划。很多题目中，动态规划并不是单一出现的，但有些例子中，这种多层次的结构并不明显，下一个例子将讨论这个问题。
交叉匹配
分析：
a[n]：存储第一行的数
    b[m]：存储第二行的数
设 f(i, j)：表示如下图所示的两行数据，可以画出的最多的匹配线段数。 3.a[i]和b[j]处，各引出一条匹配线段，这时必须a[i]≠b[j]。设a[i] = b[v]，b[j] = a[u]。从a[i]向b[v]，b[j]向a[u]各引一条匹配线段，这两条线段必然相交。这种情况的解即为f(u – 1, v – 1) + 2。
优化 ？
从什么地方入手呢？
是否要改变思路？
有更好的状态转移方程吗？
codes (ioi 1999) 码字：
  run
  rabbit
  hobbit
  stop
文本：
     stxruynvruhoabbvizxztnwrruunnp
最简覆盖序列
给定一个字码，以及它的一个覆盖序列c，若c的任何连续子序列p都不是w的覆盖序列，则称c是w的最简覆盖序列。
 例如，’alal’和’aaalal’都是’all’的一个覆盖序列，其中’alal’是’all’的最简覆盖序列，但’aaalal’却不是’all’的最简覆盖序列。显然，一个字码的最简覆盖序列必然是它的右侧最小覆盖序列，反之则不然。若一个项的覆盖序列是其对应字码的最简覆盖序列，则称之为最简项。
问题转化为：   首先必须要求出所有的最简项  ！
怎样求最简项？？ 定义：
len[i]表示第i个字码的长度。
words[i]：表示第i个字码。则words[i，1 ] .. words[i,j ]表示第i个字码的前j个字符所构成的子串。
match[i,j]：表示在当前已经读过的文本中，words[i,1..j]对应的最简覆盖序列的首位置。若存在多个这样的覆盖序列，则match[i,j]的值为首位置最大的一个；若不存在这样的覆盖序列，则match[i,j]为-∞。
例如，若words[1]=’abcd’，当前所读到的文本是’aubcavbc’，因为子串’abc’(即words[1,1..3])在当前所读到的文本中，最简覆盖序列有’aubc’和’avbc’，它们的首位置分别是1和5，因此match[1,3]=5。
如果当前读到了文本的第index个字符ch，而第i个字码的第j个字符也是ch，则有下面3种情况：
若j=1，这时令match[i,1]:=index；
若j>1，则若index-match[i,j-1]+1≤1000(项中的覆盖序列长度不超过1000)，由于words[i,1..j]和words[i,1..j-1]在当前所读到的文本中，最简覆盖序列的最大首位置应该是相同的，因此有match[i,j]:=match[i,j-1]。为了不产生非最简项，令match[i,j-1]:=-∞；
若j=len[i]且index-match[i,j]+1≤1000，则产生了一个项，且该项which:=i;st:=match[i,j];ed:=index。同时，令match[i,j]=-∞。 为了便于实现上述算法，我们建立一个字符表记录每个字符在字码集合中的位置，由于字码最多共有100*100个字符，因此该表的长度不超过10000。数组chs的定义如下：
tchar =record
  ch :char;{字符}
  i,j :byte;{该字符所在字码编号和在该字码中的位置}
end;
chs   :array[1..10000] of tchar;
为了便于检索，我们将chs以关键字ch按照字典顺序排序。由于在第二种情况中，match[i,j]利用了match[i,j-1]的信息。因此，若关键字ch相同，则以关键字j按照降序排列。
 
  设start[x]表示排序后chs中第一个ch值为x的元素的位置，则字符x在字码集合中出现的位置被记录在chs的start[x]到start[succ(x)]-1之中。
这样，找所有的项的算法为：
通过动态规划求出结果
优化？？
因为时间复杂度为o（m2），m最大为10000，为108 ，将会超时。 证明：由于vj到vk有弧，根据图g的定义，有items[j].ed<items[k].st。
又i<j，所以items[i].ed≤items[j].ed
因此items[i].ed<items[j].ed<items[k].st，这就说明vi到vk有弧。 该算法需要寻找i，在一般情况下，i与k的值十分接近，因此算法的效率要比一般动态规划高得多。题目中要求保存路径，我们在动态规划时记录决策值即可。具体程序如下：

  •items[0].ed:=0;{建立原点s} •q[0]:=0;max[0]:=0;{赋初值} •for k:=1 to m do begin •  i:=k-1;while items[k].st<=items[i].ed do dec(i);{寻找i} •  q[k]:=q[i]+len[items[k].which]; •  max[k]:=k;{max[k]是辅助数组，用于求决策值} •  if q[k-1]>q[k] then begin •    q[k]:=q[k-1]; •    max[k]:=max[k-1] •  end; •  father[k]:=max[i]{father[k]是q[k]的决策值} •end;