动态规划100例 - CSDN博客
动态规划100例
内容来自：/
更多&动态规划100例&相关资料请点击
一 资源问题.....................................................................................................................................4 资源问题 1 机器分配问题....................................................................................................4
资源问题 2 01 背包问题.......................................................................................................4 资源问题 3 系统可靠性(完全背包).....................................................................................9 资源问题 4 金明的预算方案：加花的动态规划 ..............................................................11
资源问题 5 化工场装箱员.................................................................................................15 资源问题 6 背包问题...........................................................................................................18 资源问题 7 装箱问题(判定性 01 背包).............................................................................18
资源问题 8 背包问题(+-1 背包问题+回溯)........................................................................ 18 二线性动态规划...........................................................................................................................18 线性动态规划 1 朴素最长非降子序列..............................................................................18
线性动态规划 2 日程安排 ....................................................................................................18 线性动态规划 3 组合数：..................................................................................................18 线性动态规划 4 多重历史..................................................................................................19
线性动态规划 5 最少单词个数............................................................................................19 线性动态规划 6 合唱队形..................................................................................................19 线性动态规划 7 决斗.........................................................................................................19
线性动态规划 8 舞蹈家......................................................................................................19 线性动态规划 9 (字符串)...................................................................................................19 线性动态规划 10 积木游戏..................................................................................................22
线性动态规划 11 打鼹鼠....................................................................................................22 线性动态规划 12 找数......................................................................................................23 线性动态规划 15 隐形的翅膀........................................................................................23
三 线型动态规划........................................................................................................................24 线型动态规划 1 方块消除游戏..........................................................................................24 线型动态规划 2 最长公共子串，LCS
问题......................................................................24 线型动态规划 3 IOI 2000 邮局问题.................................................................................24 线型动态规划 4 Vijos 1198 最佳课题选择.......................................................................26
线型动态规划 5 APIO2007 数据备份..............................................................................26 四 剖分问题...................................................................................................................................27 剖分问题 1 石子合并.........................................................................................................27
剖分问题 2 多边形剖分 ......................................................................................................39 剖分问题 3 乘积最大..........................................................................................................41 剖分问题 4 多边形-讨论的动态规划
................................................................................43 剖分问题 5 最大奖励..........................................................................................................44 剖分问题 6 小 H 的小屋 .....................................................................................................45
贪心的动态规划.............................................................................................................................45 贪心的动态规划 1 快餐问题..............................................................................................45 贪心的动态规划 2(过河).......................................................................................................46
计数问题.........................................................................................................................................49 计数问题 1 砝码称重..........................................................................................................49
计数问题 2 陨石的秘密......................................................................................................50 最大子矩阵.....................................................................................................................................55
最大子矩阵 1 最大 01 子矩阵 ............................................................................................55
最大子矩阵 2 最大带权 01 子矩阵....................................................................................55 最大子矩阵 3 最大字段和问题............................................................................................56 最大子矩阵问题 4 最大子立方体问题..............................................................................56
最大子矩阵问题 5 居住空间..............................................................................................56 判定性问题.....................................................................................................................................56 判定性问题
1 能否被 4 整除..............................................................................................56 判定性问题 2 能否被 k 整除 ................................................................................................56 数字三角形.....................................................................................................................................56
数字三角形 1 朴素数字三角形 ............................................................................................57 数字三角形 2 晴天小猪历险记..........................................................................................57 数字三角形 3 小胖办证......................................................................................................57
数字三角形 4 过河卒............................................................................................................57 数字三角形 5 朴素的打砖块..............................................................................................57 数字三角形 6 优化的打砖块..............................................................................................57
状态压缩动态规划.........................................................................................................................58 状态压缩动态规划 1---炮兵阵地..........................................................................................58 递推天地.........................................................................................................................................59
递推天地 1 核电站问题......................................................................................................59 递推天地 2 ------数的划分..................................................................................................60 .递推天地 3 情书抄写员........................................................................................................62
递推天地 4 错位排列..........................................................................................................64 递推天地 5 直线分平面最大区域数..................................................................................64 递推天地 6 折线分平面最大区域数..................................................................................64
递推天地 7 封闭曲线分平面最大区域数.......................................................................... 64 递推天地 8 凸多边形分三角形方法数..............................................................................64 递推天地 9 Catalan 数列一般形式.....................................................................................64
递推天地 10 彩灯布置........................................................................................................64 递推天地 11-----盒子与球..................................................................................................65 树型动态规划.................................................................................................................................66
树型动态规划 1 加分二叉树..............................................................................................66 树型动态规划 2 选课 ..........................................................................................................70 树形动态规划 3 贪吃的九头龙..........................................................................................74
树形动态规划 4 有线电视网................................................................................................79 树形动态规划 5 有向树 k 中值问题....................................................................................79 树形动态规划 6 聚会的快乐..............................................................................................79
树形动态规划 7 .皇宫看守.................................................................................................79 树形动态规划 8 -----APIO2007 风铃...................................................................................80 树形动态规划 9-----CTSC 2001 选课...................................................................................80
树形动态规划 10（双次记录）............................................................................................81 树形动态规划 11(完全二叉树) NOI2006 网络收费 ........................................................... 83 树形动态规划 12 千年虫.......................................................................................................85
树形动态规划 13 IOI2005 河流...........................................................................................87 树形动态规划 14 -----访问术馆............................................................................................88 地图动态规划.................................................................................................................................89
地图动态规划 1 NOI 2005 adv19910...................................................................................89 地图动态规划-2----优化的 NOI 2005adv19910 .................................................................. 89 地图动态规划 3 vijos 某题...............................................................................................89
目标动态规划.................................................................................................................................90 目标动态规划 1 CEOI98 subtra.............................................................................................90
目标动态规划 2 Vijos 1037 搭建双塔问题....................................................................... 90 概率动态规划.................................................................................................................................90 概率动态规划 1-----聪聪和可可(NOI2005).........................................................................
90 概率动态规划 2 血缘关系 ..................................................................................................90 其他类型.........................................................................................................................................91
1 记忆化搜索..........................................................................................................................91 2 状态压缩动态规划..............................................................................................................91 3
字符串动态规划..................................................................................................................96 4 多进程动态规划.................................................................................................................96 5 多进程动态规划.................................................................................................................96
6 多进程动态规划..................................................................................................................96 7 括号序列.............................................................................................................................97
8 棋盘切割.............................................................................................................................97 9 最短路 1............................................................................................................................100
10 双重动态规划.................................................................................................................101 11 动态规划.........................................................................................................................101
12 动态规划.........................................................................................................................101 13 动态规划.........................................................................................................................101
14 动态规划.........................................................................................................................101 15 动态规划.........................................................................................................................101
16 动态规划.........................................................................................................................102 17 动态规划.........................................................................................................................102
18 动态规划.........................................................................................................................102 19 描述 Description.............................................................................................................103
20、描述 Description..........................................................................................................103
一 资源问题
资源问题 1 机器分配问题 ----总公司拥有高效生产设备 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]+w[i,j-k]) 资源问题 2 01 背包问题
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]); * 一个旅行者有一个最多能用 M 公斤的背包，现在有 N 件物品， 它们的重量分别是 W1，W2，...,Wn, 它们的价值分别为 P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式：M,N W1,P1 W2,P2 ...... 输出格式： X */ 因为背包最大容量 M 未知。所以，我们的程序要从 1 到M 一个一个的试。比如，开 始任选 N 件物品的一个。看对应M 的背包，能不能放进去，如果能放进去，并且还有多的空
间，则，多出来的空间里能放 N-1 物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。 测试数据： 10,3 3,4 4,5 5,6
c[i][j]数组保存了 1,2,3 号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为 0 开始,1 号物品先试,0,1,2,的容量都不能放.所以置 0,背包容量为 3 则里面放 4.这样,这一排背包容量为 4,5,6,....10 的时 候，最佳方案都是放 4.假如 1 号物品放入背包.则再看 2 号物品.当背包容量为 3 的时候， 最佳方案还是上一排的最价方案 c 为 4.而背包容量为 5 的时候，则最佳方案为自己的重量 5.背包容量为 7 的时候， 很显然是5 加上一个值了。 加谁??很显然是
7-4=3 的时候.上一排 c3 的最佳方案是 4.所以。总的最佳方案是 5+4 为 9.这样.一排一排推下去。 最右下放的数据就 是最大的价值了。(注意第 3 排的背包容量为 7 的时候,最佳方案不是本身的 6.而是上一排 的 9.说明这时候 3号物品没有被选.选的是 1,2 号物品.所以得 9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程. 这回清楚了吗? 下面是实际程序:#include&stdio.h&
int c[10][100];/*对应每种情况的最大价值*/int knapsack(int m,int n) { int i,j,w[10],p[10]; for(i=1;i&n+1;i++)scanf(&\n%d,%d&,&w[i],&p[i]); for(i=0;i&10;i++)for(j=0;j&100;j++) c[i][j]=0;/*初始化数组*/for(i=1;i&n+1;i++) for(j=1;j&m+1;j++) { if(w[i]&=j) /*如果当前物品的容量小于背包容量*/ {
if(p[i]+c[i-1][j-w[i]]&c[i-1][j]) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
/*大于上一次选择的最佳方案则更新 c[i][j]*/c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; } else c[i][j]=c[i-1][j];} return(c[n][m]);
} int main() { int m,n;int i,j; scanf(&%d,%d&,&m,&n);printf(&Input each one:\n&); printf(&%d&,knapsack(m,n));printf(&\n&);/*下面是测试这个数组,可删除*/ for(i=0;i&10;i++) for(j=0;j&15;j++) { printf(&%d&,c[i][j]); if(j==14)printf(&\n&); } system(&pause&);}
//程序名称：动态规划解 0-1 背包问题#include&iostream& #include&iomanip&
const int MAX=1000; int w[MAX],v[MAX],best[MAX]; int V[MAX][MAX]; //最大价值矩阵 int W,n; //W 为背包的最大载重量，n 为物品的数量
//求最大值函数 int max(int x,int y) { return x &= y?x:y; }
//求最小值函数 int min(int x,int y) { return x&= y ? y:x;}
void Knaspack() { int Max=min(w[n]-1,W); for(int j=1; j &= M j++)V[n][j]=0; for( int j=w[n]; j &= W ; j++) V[n][j]=v[n]; for(int i=n-1;i &1 ; i--) { Max=min(w[i]-1,W); for(int j=1; j &= M j++)V[i][j]=V[i+1][j];
for(int j=w[i]; j &= W; j++) V[i][j]=max(V[i+1][j],V[i+1][j-w[i]]+v[i]); }V[1][W]=V[2][W]; //先假设第一个物品不放入 if(W & w[1])V[1][W]=max(V[1][W],V[2][W-w[1]]+v[1]); }
//生成向量数组，决定某一个物品是否应该放入背包
void Traceback() { for(int i=1; i & i++) 的最优值. {if(V[i][W] == V[i+1][W]) 等，则表明该物品不能放入。 best[i]=0; else{ best[i]=1; W-=w[i]; } } best[n]=(V[n][W] )?1:0; } //否则可以放入 //如果当前行的最优值与下一行的最优值相 //比较矩阵两邻两行(除最后一行)，背包容量为 W
void main() { cout&&&输入商品数量 n 和背包容量 W:&; cin&&n&&W;
cout&&&输入每件商品的重量 w:&&&for(int i=1;i&=n;i++) cin&&w[i]; cout&&&输入每件商品的价值 v:&&& for(int i=1;i&=n;i++) cin&&v[i];memset(V,0,sizeof(V)); Knaspack();//构造矩阵 Traceback();//求出解的向量数组
int totalW=0;
int totalV=0; //显示可以放入的物品 cout&&&所选择的商品如下:&&& cout&&&序号 i:重量 w:价格 v:&&&
for(int i=1; i &= i++) { if(best[i] == 1) { totalW+=w[i]; totalV+=v[i];cout&&setiosflags(ios::left)&&setw(5)&&i&&&&&&v[i]&& } } cout&&&放入的物品重量总和是:&&&totalW&&& 价值最优解是:&&&V[1][W]&&&&&&totalV&& } 资源问题 3 系统可靠性(完全背包) &&&w[i]&&&
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的 费用是 c，价值是 w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]} 系统可靠性 一个 系统由若干部件串联而成， 只要有一个部件故障， 系统就不能正常运行，为 提高系统的可靠性， 每一部件都装有备用件， 一旦原部件故障， 备用件就自 动进入系统。 显然备用件越多， 系统可靠性越高，但费用也越大， 那么在一 定总费用限制下，系统的最高可靠性等于多少？ 给定一些系统备用件的单价 Ck， 以及当用 Mk个此备用件时部件的正常工作概率 Pk（Mk） ，总费用 上限 C。 求系统可能的最高可靠性。 输入文件格式：第一行：
n C第二行： C1 P1 (0) P1 (1 ) ? P1 (X1 ) （0&=X1 &=[C/Ck] ） ? 第 n 行： Cn Pn(0) Pn(1 ) ? Pn(Xn) （0&=Xn&=[C/Cn] ）分析 例： 输入： 2 20 3 0 . 60.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?Ck*Cost[I] ] *P[I,
k] } (0&=I&=n, 0&=K&= money div Cost(I) ) 初始： F[0, 0] =0 目标： F[n, C]
1．证明这个问题符合最优化原理。可以用反证法证明之。假设用 money 的资金购买了前 I 项备用件，得到了最高的系统可靠性，而且又存在如下情况：对于备用件 I，设要买 Ki 个， 则可用的资金还剩余 money ?C Ci*Ki，用这些钱购买前 （I-1） 项备用件， 如果存在一种前 （I-1）种备用件的购买方案得到的系统可靠性比当前得到的要高， 那么这个新的方案会使得整个前 I 项备用件组成的系统可靠性比原先的更高，与原假设矛盾。所以可以证明这个问题符合最优化原理。 2．证明这个问题符合无后效性原则。 3．综上所述，本题适合于用动态规划求解。
4．递推方程及边界条件： F[I,money] := max {F[I-1,money ?C C[I]*K[I] ] } (0&=K[I]&= C div Ci ) 三、参考程序
{$Q-,R-,S-} {$M 360} Program system_ constfinp='input.txt'; fout='output.txt'; maxm=3000; var f,p:array[0..maxm]max,v: c,co,e,i,j,k,m,n: var output: beginassign(output,fout); rewrite(output);
writeln(f[c]:1:4); close(output);Begin assign(input,finp); reset(input); readln(input,n,c); for i:=0 to c dof[i]:=1; for i:=1 to n do begin read(input,co); m:= for e:=0 to m doread(input,p[e]); for j:=c downto 0 do begin m:= max:=0;
for k:=0 to mdo begin v:=f[j-k*co]*p[k]; if v&max then max:=v; f[j]:=
close(input); print End.
资源问题 4
-金明的预算方案
金明的预算方案 (budget.pas/c/cpp) 【问题描述】 金明今天很开心， 家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房 间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪 些物品，怎么布置，你说了算，只要不超过 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]。 （其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件budget.in 的第 1 行，为两个正整数，用一个空格隔开： N m （其中 N（&32000）表示总钱数，m（&60）为希望购买物品的个数。 ） 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q （其中 v 表示该物品的价格（v&10000） 表示该物品的重要度（1~5） 表示该物品是主 ，p ，q 件还是附件。如果 q=0，表示该物品为主件，如果
q&0，表示该物品为附件，q 是所属主件 的编号） 【输出文件】 输出文件 budget.out 只有一个正整数， 为不超过总钱数的物品的价格与重要度乘积的总和的 最大值（&200000） 。 【输入样例】
400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200
f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p [fa]);
如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是 多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经 典的背包问题 了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的 dp 题目。可惜我当时没做出来。 草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动
规方程：f[i,j]:=f[i-1,j]; if (i 为主件 or i 的附件在包中）and (f[i,j]&f[i,j-v]+v*w) then f[i,j]:=f[i,j-v]+v*w; 我们来分析一下复杂度，空间：dp 的阶段为 n^2,对与每一个阶段都要记录该状态下在 包中的物品有哪些（因为要确定附件的主件是否在包中)， 每个阶段的 记录都要 O(n)的空间，所以总的就是 O(n^3)。时间，一个 dp，n^2 的外层循环，内部用布尔量加个主附件的对应 数组，为 O(1)，和起来就为 O(n^2)的复杂度。
可以看的出，时间的需求为 32000*60，不成问题。空间 ，大约要 7.5M 的 空间，在 64M 的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是 10 元的整数倍”，就可以把速度在提高十倍。 细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个 附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。 对于一套物品（包含主件，所以的附件） ，我们称为一个属类，对一个属类的物品的购
买方法，有以下５种： １.一个都不买 ２.主件 ３.主件＋附件１４.主件＋附件２ ５.主件＋附件１＋附件２ 这五种购买方法也是唯一的五种方法，也就是说对一属类的物品， 我们只有上述的５种 购买方法。 于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。 这样我们把物品的属类 作为 dp 的状态。可以得到如下的 dp 方程： f[i,j]=max{f[i-1,j];
f[i-1,j-v[i,0]]+v[i,0]*w[i,0];f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2]; f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}很显然时间复杂度为 O(n^2)，空间复杂度为 O(n^2)，加上利用“每件物品都是 10 元的 整数倍”除以
10 的优化，本题就很完美的解决了。 （附程序） ； programQi(input,output); type node=record u: v:array[0..2]p:array[0..2] var n,m,k: w:array[1..60]f:array[0..60,0..3200] g:array[1..60]var
i,j: vx,px,qx:array[1..60] begin readln(n,m); k:=0; fori:=1 to m do begin readln(vx,px,qx); if qx=0 then begin k:=k+1; g:=k; with w[k]do begin u:=0; v[0]:= p[0]:= for j:=1 to 2 do begin v[j]:=0; p[j]:=0; for i:=1
to m do if qx&&0 then begin with w[g[qx]] do
begin u:=u+1; v:= p:= for i:=1 to k do with w do begin for j:=0to 2 do write('(',v[j],',',p[j],') '); vari,j: begin fillchar(f,sizeof(f),0); for i:=1 to k do with w do beginfor j:=1 to n do begin f[i,j]:=f[i-1,j];
if (j&=v[0]) and(f[i,j]&f[i-1,j-v[0]]+v[0]*p[0]) then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0]; if(j&=v[0]+v[1]) and (f[i,j]&f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1]) thenf[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1]; if (j&=v[0]+v[2]) and(f[i,j]&f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2])
then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];if (j&=v[0]+v[1]+v[2]) and(f[i,j]&f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2]) thenf[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2]; begin writeln(f[k,n]);
资源问题 5 化工场装箱员 118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高， 技术不是十分完善， 所以工厂生产的锎成品可能会有3种不同的纯 度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员 grant 第1次顺序从流水线上取10个成品 （如果一 共不足10个，则全部取出） ，以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部 取出不足10 个，则全部取出） ，如果所有的成品都装进了箱子，那么
grant 的任务就完成了。 ?? 由于装箱是件非常累的事情，grant 希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。 【输入格式】 第1行为 n（1&=n&=100） ，为成品的数量 以后 n 行，每行为一个大写字母 A，B 或 C，表示成品的纯度。【输出格式】 仅一行，为 grant 需要的最少的装箱次数。 【输入样例】worker.in11 A B C A B C A B C A B 【输出样例】worker.out 3 viewsourceprint? 01 //动态规划 02
#include&cstdio& 03#include&cstdlib& 04 intn,i; 05 intf[150][11][11][11]; 06boolg[150][11][11][11]; 07 intdata[150]; 08 09 intmin(inta,intb) 10 {
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
if(a&b) } intdp(intk,inta,intb,intc) { inti,j=a+b+c;for(i=1;i&=10-j;i++) { k++; if(k&n) if(data[k]==1) a++;if(data[k]==2) b++; if(data[k]==3) c++; } if(k&=n) { g[n][a][b][c]=1;f[n][a][b][c]=(a&0)+(b&0)+(c&0); returnf[n][a][b][c]; }if(!g[k][a][b][c])
{ g[k][a][b][c]=1; f[k][a][b][c]=100000;
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
if(a&0) f[k][a][b][c]=min(f[k][a][b][c],dp(k,0,b,c)+1); if(b&0)f[k][a][b][c]=min(f[k][a][b][c],dp(k,a,0,c)+1); if(c&0) f[k][a][b][c]=min(f[k][a][b][c],dp(k,a,b,0)+1);} returnf[k][a][b][c]; }
intmain() { freopen(&worker.in&,&r&,stdin);//freopen(&worker.out&,&w&,stdout);scanf(&%d\n&,&n); for(i=1;i&=n;i++) {scanf(&%c\n&,&c); data[i]=c-64; } intans=dp(0,0,0,0); printf(&%d\n&,ans);//system(&pause&); return0; }
资源问题 6 背包问题
----- USACO Raucous Rockers 多个背包，不可以重复放物品，但放物品的顺序有限制。F[I,j,k]表示决策到第 i 个物品、第 j 个背包，此背包花费了 k 的空间。f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t])
资源问题 7 装箱问题(判定性 01 背包)
f[j]:=(f[j] or f[j-v]);
资源问题 8 背包问题(+-1 背包问题+回溯)
-----CEOI1998 Substract f[i,j]:=f[i-1,j-a] or f[i-1,j+a]
二 线性动态规划
线性动态规划 1 朴素最长非降子序列
设有由 n 个不相同的整数组成的数列， 记为: a(1)，a(2)，??，a(n)且 a(i)&&a(j) (i&&j) 例如 3，18，7，14，10，12，23，41，16，24。 若存在 i1& ? & ie 且有 a(i1)& ? 则称为长度为 e 的不下降序列。如上例中 3，18，23，24 就是一个长度为 4 的不下降序列，同时也有 3，7，10，12，16， 24 长度为 6 的不下降序列。程序要求，当原数列给出之后，求出最长的不下降 序列。F[i]:=max{f[j]+1}
线性动态规划 2 日程安排
-----f:=max{f[j]}+P[I]; (e[j]&s)
线性动态规划 3 组合数：
描述 Description 组合公式C=N!/(M!*(N-M)!). 问题是求 C 中不同的质因子的个数 例如 N=7, M=4. C=7!/(3!*4!)=)=35=5*7. 则不同的质因子的个数为 2 （分别是 5，7）。
输入格式 Input Format 输入 N，M ??(1 &= N, M &= 50000) 输出格式 OutputFormat 输出一个整数 样例输入 Sample Input
样例输出 Sample Output
线性动态规划 4 多重历史
----f[i,j]:=sigma{f[i-k,j-1]}(if checked)
线性动态规划 5 最少单词个数
-----最少单词个数 f[i,j]:=max{f[I,j],f[u-1,j-1]+l}
线性动态规划 6 合唱队形
------合唱队形 两次 F:=max{f[j]+1}＋枚举中央结点
线性动态规划 7 决斗
-----决斗 F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] ore[j,k]),i&k&j
线性动态规划 8 舞蹈家
F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])
线性动态规划 9 (字符串)
-----NOI 2000 古城之谜古城之谜
著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。 让教授欣喜的是在这个他称为冰 峰城(Ice-PeakCity)的城市中有 12 块巨大石碑，上面刻着用某种文字书写的资料，他称这种文 字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。幸好当时教授把石碑上的文字都拍摄了下来， 为了解开冰峰城的秘密， 教授和他的助手牛博士开 始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词(n)、动词(v)、辅词(a)这三类单词，且其文法很简单： ? &文章& ::= &句子& { &句子& } ? &句子&
::= &陈述句& ? &陈述句& ::= &名词短语& { &动词短语& &名词短语& } [ &动词短语& ] ? &名词短语& ::= &名词& | [ &辅词& ] &名词短语& ? &动词短语& ::= &动词& | [ &辅词& ] &动词短语& ? &单词& ::= &名词& | &动词& | &辅词& 注：其中&名词&、&动词&和&辅词&由词典给出，“::=”表示定义为，“|”表示或，{}内的项可以重 复任意多次或不出现，[]内的项可以出现一次或不出现。 在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有
26 个字母，为了研究方 便，用字母 a 到 z 表示它们。 冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符， 因此划分单词和句子令石教授和 牛博士感到非常麻烦，于是他们想到了使用计算机来帮助解决这个问题。假设你接受了这份工 作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文 章划分为最少的单词。 [输入文件] ? 输入文件第 1 行为词典中的单词数 n（n&=1000）。 ? 输入文件第 2 行至第(n+1)行每行表示一个单词，形为“α.mot”， α 表示词性，可
能是n(名词),v（动词）,a（辅词）中的一个，mot 为单词，单词的长度不超过 20。拼写相同而词性不同的单词视为不同的单词，如输入示例中的 n.kick 与 v.kick 是两个不同的单词。 ? 输入文件第(n+2)行为需要划分的文章，以“.”结束。 ? 输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过 5KB。 [输出文件]
? 输出文件为两行，每行一个整数。 ? 输出文件第 1 行为划分出来的句子数。 ? 输出文件第 2 行为划分出来的单词数。 [输入输出文件样例] Input
11 n.table n.baleine a.silly n.snoopy n.sillysnoopy v.is v.isnot n.kick v.kicka.big v.cry sillysnoopyisnotbigtablebaleinekicksnoopysillycry.
[样例说明] （为了阅读方便，划分的单词用空格分隔，在单词右标出它的词性，每行写一个句子，用句号表示句子结束。） 输出对应的划分：
sillysnoopy[n] isnot[v] big[a] table[n]. baleine[n] kick[v] snoopy[n] silly[a]cry[v].
如果用下面的划分：
silly[a] snoopy[n] isnot[v] big[a] table[n].
baleine[n] kick[v] snoopy[n] silly[a] cry[v].
则划分的句子数仍为 2 个，但单词数却多了 1 个，为 10 个，显然应该按前者而不是后者划分。
线性动态规划 10 积木游戏
-----积木游戏F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’]) 积木游戏（NOI’97） 一种积木游戏，游戏者有 N 块编号依次为 1，2，?，N 的长方体积木。第 I 块积 木通过同一顶点三条边的长度分别为 ai,bi,ci（i=1,2,?,N），如图 1 所示：
游戏规则如下： 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 根柱子的高度之和。
线性动态规划 11 打鼹鼠
-----打鼹鼠’描述 Description 根据这个特点阿 Q 编写了一个打鼹鼠的游戏：在一个 n*n 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 i 时刻鼹鼠在某个网格中出现，而机器人也处于同一 网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格， 即从坐标为 （i,j） 的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1) 四个网格，机器人不能走出整个
n*n 的网格。游戏开始时，你可以自由选定机器人的初始位置。
现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽 可能多的鼹鼠。 输入格式 Input Format 文件第一行为 n（n&=1000）, m（m&=10000），其中 m 表示在这一段时间内出现的鼹鼠的个数，接下 来的 m 行每行有三个数据 time,x,y 表示有一只鼹鼠在游戏开始后 time 个时刻，在第 x 行第 y 个网格里出 现了一只鼹鼠。Time 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出 现一只鼹鼠。 输出格式 Output
Format 输出文件中仅包含一个正整数，表示被打死鼹鼠的最大数目。 样例输入 Sample Input
2 2 1 1 1 2 2 2
样例输出 Sample Output
线性动态规划 12 找数
-----找数 线性扫描 sum:=f+g[j]; (if sum=A ifsum&Aim then inc(i) else inc (j);)
线性动态规划 15
背景 Background
隐形的翅膀
——隐形的翅膀
小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。 （小杉是怎么看到的？??） 描述 Description 天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。现在天使给了小杉 N 只翅膀，小杉想挑出一对最完美的。 输入格式 InputFormat 每组测试数据的 第一行有一个数 N(2&=N&=30000) 第二行有 N 个不超过 1e5 的正整数，表示N 只翅膀的长度。 20%的数据 N&=100 输出格式 Output Format 对每组测试数据输出两个整数，分两行，表示小杉挑选出来的一对翅膀。
注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。样例输入 Sample Input
样例输出 Sample Output
2 3 三 线型动态规划
线型动态规划 1 方块消除游戏
-----方块消除游戏 f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]} ans:=f[1,m,0]
线型动态规划 2 最长公共子串，LCS 问题
-----最长公共子串，LCS 问题f[i,j]={0(i=0)&(j=0); f[i-1,j-1]+1 (i&0,j&0,x=y[j]);max{f[i,j-1]+f[i-1,j]}} (i&0,j&0,x&&y[j]);
线型动态规划 3 IOI 2000 邮局问题 [问题描述] 按照递增顺序给出一条直线上坐标互不相同的 n 个村庄， 要求从中选择 p 个村庄建立邮 局， 每个村庄使用离它最近的那个邮局， 使得所有村庄到各自所使用的邮局的距离总和最小。 试编程计算最小距离和，以及邮局建立方案。 [算法分析] 本题也是一道动态规划问题，详细分析请看文本附件（邮局解题报告）。将 n 个村庄按 坐标递增依次编号为 1，2，??，n，各个邮局的坐标为 d[1..n]，状态表示描述为：m[i,j] 表示在前 j 个村庄建立i 个邮局的最小距离和。所以，m[p,n]即为问题的解，且状态转移
方程和边界条件为： m[1,j]=w[1,j] i≤j 其中 w[i,j]表示在 d[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个 邮 局 时 ， 最 优 解 出 现 在 中 位 数 ，即 设 建 立 邮 局 的 村 庄 为 k ， 则
i ?1? k ? j ?1
m[i, j ] ? min {m[i ? 1, k ] ? w[k ? 1, j ]}
k ? ?(i ? j ) / 2?或k ? ?(i ? j ) / 2? ，于是，我们有：
， k ? ?(i ? j ) / 2?或k ? ?(i ?j ) / 2? 同时，令 s[i,j]=k，记录使用前i-1 个邮局的村庄数，便于在算出最小距离和之后构造 最优建立方案。 上述算法中 w[i,j]可通过 O(n)时间的预处理，在 O(1)的时间内算出，所以，该算法 的状态总数为 O(n*p)，每个状态转移的状态数为 O(n)，每次状态转移的时间为 O(1)，该 算法总的时间复杂度为 O(p*n2)。 [算法优化] 本题的状态转移方程与①式十分相似，因此我们猜想其决策是否也满足单调性，即 s[i-1,j]≤s[i,j]≤s[i,j+1]
首先，我们来证明函数 w 满足四边形不等式，即：
w[i, j ] ? ? | d [l ] ? d [k ] |
w[i, j ] ? w[i' , j ' ] ? w[i' , j ] ? w[i, j ' ] , i ? i' ? j ? j ' 设 y ? ?(i'? j ) / 2? ， z ? ?(i ? j ' ) / 2? ，下面分为两种情形，z≤y 或 z&y，下面仅讨论
z≤y，z&y 的情况是类似的。 由 i≤z≤y≤j 有：
w[i, j ] ? w[i ' , j ' ] ? ? | d [l ] ? d [ z ] | ? ? | d [l ] ? d [ y ] |
l ?i l ?i '
? ? | d [l ] ? d [ z ] | ? ? | d [l ] ? d [ y ] | ?
l ?i j' l ?i ' j
? | d [l ] ? d [ z ] | ? ? | d [l ] ? d[ y] |
? ? | d [l ] ? d [ z ] | ? ? | d [l ] ? d [ y ] |
l ?i l ?i '
? w[i ' , j ] ? w[i, j ' ]
接着，我们用数学归纳法证明函数 m 也满足四边形不等式。对四边形不等式中“长度” l=j’-i 进行归纳： 当i=i’或 j=j’时，不等式显然成立。由此可知，当 l≤1 时，函数 m 满足四边形不等式。 下面分两种情形进行归纳证明： 情形 1：i&i’=j&j’，即 m[i,j]+m[j,j’] ≤m[i,j’]，设 k=max{p | m[i,j’]=m[i,p-1]+m[p,j’]+w[i,j’] }，再分两种情形 k≤j 或 k&j。 下面只讨论k≤j，k&j 的情况是类似的。
m[i, j ] ? m[ j, j ' ] ? m[i ? 1, k ] ? w[k ? 1, j ] ? m[ j ? 1, j ? 1] ? w[ j,j ' ] ? m[i ? 1, k ] ? w[k ? 1, j ' ] ? m[i, j ' ]
情形 2：i&i’&j&j’ 设 y=max{p | m[i’,j]=m[i’-1,p]+w[p+1,j] } z=max{p |m[i,j’]=m[i-1,p]+w[p+1,j’] } 仍需再分两种情形讨论，即 z≤y 或 z&y。 情形 2.1，当z≤y&j&j’时：
m[i, j ] ? m[i' , j ' ] ? m[i'?1, y] ? w[ y ? 1, j ' ] ? m[i ? 1, z ] ? w[ z ?1, j ] ? m[i'?1, y] ? m[i ? 1, z ] ? w[ y ? 1, j ] ? w[ z ? 1, j ' ] ? m[i' , j] ? m[i, j ' ]
情形 2.2，当i-1&i’-1≤y&z&j’时：
m[i, j ] ? m[i' , j ' ] ? m[i ? 1, y ] ? w[ y ? 1, j ] ? m[i'?1, z ] ? w[ z ?1, j ' ] ? m[i ? 1, z ] ? m[i'?1, y ] ? w[ y ? 1, j ] ? w[ z ? 1, j ' ]; ? m[i,j ' ] ? m[i' , j ]
最后，我们证明决策 s[i,j]满足单调性。 为讨论方便，令mk[i,j]=m[i-1,k]+w[k+1,j]； 我们先来证明 s[i-1,j]≤s[i,j]，只要证明对于所有 i≤k&k’&j 且 mk’[i-1,j]≤mk[i-1,j]，有：mk’[i,j]≤mk[i,j]。 类似地，我们可以证明一个更强的不等式mk[i-1,j]-mk’[i-1,j]≤mk[i,j]-mk’[i,j] 也就是：mk[i-1,j]+mk’[i,j]≤mk[i,j]+mk’[i-1,j] 利用递推定义式展开整理的：m[i-2,k]+m[i-1,k’]≤m[i-1,k]+m[i-2,k’]，这就是
i-2&i-1&k&k’时 m 的四边形不等式。 我们再来证明 s[i,j]≤s[i,j+1]，与上文类似，设 k&k’&j，则我们只需证明一个更强的不等式： mk[i,j]-mk’[i,j]≤mk[i,j+1]-mk’[i,j+1] 也就是： mk[i,j]+mk’[i,j+1]≤mk[i,j+1]+mk’[i,j] 利用递推定义式展开整理的：w[k+1,j]+w[k’+1,j+1]≤w[k+1,j+1]+w[k’+1,j]， 这就是 k+1&k’+1&j&j+1 时 w 的四边形不等式。综上所述，该问题的决策
s[i,j]具有单调性，于是优化后的状态转移方程为：m[1,j]=w[1,j]
m[i, j ] ?
s[ i ?1, j ]? k ? s[ i , j ?1]
{m[i ? 1, k ] ? w[k ? 1, j ]}
s[i,j]=k 同上文所述，优化后的算法时间复杂度为 O(n*p)。
-----IOI 2000 邮局问题f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);
线型动态规划 4 Vijos 1198 最佳课题选择
-----Vijos 1198 最佳课题选择 if j-k&=0 thenMin(f[i,j],f[i-1,j-k]+time(i,k));
线型动态规划 5 APIO2007 数据备份
-----APIO2007 数据备份 状态压缩＋剪掉每个阶段 j 前 j*2 个状态和 j*2+200 后的状态贪心动态规划 f:=min(g[i-2]+s,f[i-1]);
四 剖分问题
剖分问题 1 石子合并
-----石子合并 在一个园形操场的四周摆放 N 堆石子（N≤100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该 次合并的得分。 编一程序，由文件读入堆数 N 及每堆的石子数（≤２０）。 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);一．试 题 在一个园形操场的四周摆放 N 堆石子（N≤100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该 次合并的得分。 编一程序，由文件读入堆数N
及每堆的石子数（≤２０）， ①选择一种合并石子的方案，使得做 N－1 次合并，得分的总和最小； ②选择一种合并石子的方案，使得做 N－1 次合并，得分的总和最大。 例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为４５９４。 则３次合并得分总和最小的方案：８＋１３＋２２＝４３ 得分最大的方案为：１４＋１８＋２２＝５４ 输入数据： 文件名由键盘输入，该文件内容为：第一行为石子堆数 N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为 output.txt
从第 1 至第N 行为得分最小的合并方案。第 N＋1 行是空行。从第 N＋2 行到第 2N＋1 行是得 分最大合并方案。 每种合并方案用 N 行表示，其中第 i 行（1≤i≤N）表示第 i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。 要求将待合并的两堆石子数以 相应的负数表示，以便标识。 输入输出范例： 输入文件内容： ４ ４ ５９ ４
输出文件内容： －４ ５ ９ －４ －８－５ ９ －１３ －９ ２２ ４ －５ －９ ４ ４ －１４ －４ －４－１８ ２２ 二．算法分析 竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面 的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大） 的相邻两堆合并， 形成新的一堆；接下来，在N－1 堆中选得分最小（最大）的相邻两堆合 并??，依次类推，直至所有石子经 N－1 次合并后形成一堆。 例如有６堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为３４６ ５ ４ ２ 要求选择一种合并石子的方案，使得做５次合并，得分的总和最小。
按照贪心法，合并的过程如下： 每次合并得分 第一次合并 ３ ４ ６ ５ ４ ２ -&５ 第二次合并 ５ ４ ６ ５ ４ -&９ 第三次合并 ９６ ５ ４ -&９ 第四次合并 ９ ６ ９ -&１５第五次合并 １５ ９ -&２４ 24 总得分＝５＋９＋９＋１５＋２４＝６２但是当我们仔细琢磨后，可得出另一个合并石子的方案： 每次合并得分 第一次合并 ３ ４ ６ ５ ４ ２ -&７第二次合并 ７ ６ ５ ４ ２ -&１３ 第三次合并 １３ ５ ４ ２-&６ 第四次合并 １３ ５ ６ -&１１ 第五次合并 １３ １１
-&２４ 24 总得分＝７＋６＋１１＋１３＋２４＝６１ 显然，后者比贪心法得出的合并方案更优。题目中的示例故意造成一个 贪心法解题的
假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来， 我们先来明确一个问题： １．最佳合并过程符合最佳原理 使用贪心法至所以可能出错，是因为每一次选择得分最小（最大）的相邻两堆合并，不一定保证余下的 合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果 N－1 次 合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的 N－1 次 合并后的得分总和必然是最优的。 例如上例中第五次合并石子数分别为１３和１１的相邻两堆。这两堆石头分别由最初的第１，２，３堆（石头数分别为３，４，６）和
第４，５，６堆（石头数分别为５，４，２）经４次合并后形成的。于是问题又 归结为如何使得这两个子序列的 N－2 次合并的得分总和最优。 为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１， 第３堆为子序列２。第一次合并子序列１中的两堆，得分７； 第二次再将之与子序列２的一堆合并，得分１３。显然对于第１个子序列 来说，这样的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列 １，第５，６堆构成子序列２。第三次合并子序列２中的２堆，得 分６；第四次再将之与子序列１中的一堆合并，得分１３。显然对于第二个子序
列来说，这样的合并方案也是最优的。 由此得出一个结论──６堆石子经 过这样的５次合并后，得分的总和最小。我们把每一次合并划分为阶段，当前阶段中计算出的得分和作为状态， 如何在前一次合并的基础上定义一个能使目前得分总和最大的合并方案 作为一次决策。很显然，某阶段的状态给定后，则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性质符最佳原理，因此可以用动态规划的算法求解。 ２．动态规划的方向和初值的设定 采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。这 些石子堆子序列包括： ｛第１堆、第２堆｝、｛第２堆、第３堆｝、??、｛第N
堆、第１堆｝； ｛第１堆、第２堆、第３堆｝、 ｛第２堆、第３堆、第４堆｝、??、 ｛第 N 堆、第１堆、第２堆｝；?? ｛第１堆、??、第 N 堆｝｛第１堆、??、第 N 堆、第１堆｝??｛第 N 堆、第１堆、??、第 N－１堆｝ 为了便于运算，我们用〔i，j〕表示一个从第 i 堆数起，顺时针数 j 堆时 的子序列｛第 i 堆、第 i＋１堆、??、第（i＋j－1）mod n 堆｝ 它的最佳合并方案包括两个信息： ①在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和； ②形成最佳得分和的子序列１和子序列２。由于两个子序列是相邻的，
因 此只需记住子序列１的堆数； 设
f〔i，j〕──将子序列〔i，j〕中的 j 堆石子合并成一堆的最佳得分和； c〔i，j〕──将〔i，j〕一分为二，其中子序列１的堆数；（１≤i≤N，１≤j≤N） 显然，对每一堆石子来说，它的 f〔i，１〕＝０ c〔i，１〕＝０ （１≤i≤N） 对于子序列〔i，j〕来说，若求最小得分总和，f〔i，j〕的初始值为∞； 若求最大得分总和，f〔i，j〕的初始值为０。（１≤i≤N，２≤j≤N）。 动态规划的方向是顺推(即从上而下)。先考虑含二堆石子的 N 个子序列（各子序列分别从第１堆、第２堆、??、第 N 堆数起，顺时针数２堆）的合并方案
f〔１，２〕，f〔２，２〕，??，f〔N，２〕 c〔１，２〕，c〔２，２〕，??，c〔N，２〕 然后考虑含三堆石子的Ｎ个子序列（各子序列分别从第１堆、第２ 堆、??、第Ｎ堆数起，顺时针数３堆）的合并方案 f〔１，３〕，f〔２，３〕，??，f〔N，３〕 c〔１，３〕，c〔２，３〕，??，c〔N，３〕 ?? 依次类推， 直至考虑了含 N 堆石子的 N 个子序列 （各子序列分别从第１堆、 第２堆、 ??、第 N 堆数起，顺时针数 N 堆）的合并方案 f〔１，N〕，f〔２，N〕，??，f〔N，N〕 c〔１，N〕，c〔２，N〕，??，c〔N，N〕
最后，在子序列〔１，N〕，〔２，N〕，??，〔N，N〕中，选择得分总和（f 值）最小（或最大）的一个子序列〔i，N〕（１≤i≤N），由此出发倒推 合并过程。 ３．动态规划方程和倒推合并过程对子序列〔i，j〕最后一次合并，其得分为第 i 堆数起，顺时针数 j 堆的 石子总数 t。被合并的两堆石子是由子序列〔i，k〕和〔（i＋k－１）mod n＋１，j－k〕（１≤k≤j－１）经有限次合并形成的。为了求出最佳合并方案中的 k 值，我们定义一个动态规划方程： 当求最大得分总和时 f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
１≤k≤j－１ c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t （２≤ｊ≤ｎ，１≤ｉ≤ｎ） 当求最小得分总和时 f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝ １≤k≤j－１ c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t （２≤ｊ≤ｎ，１≤ｉ≤ｎ） 其中 x＝（i＋k－１）modn＋１，即第 i 堆数起，顺时针数 k＋１堆的堆 序号。
例如对上面例子中的６(３ ４ ６ ５ ４ ２ )堆石子，按动态规划方程顺 推最小得分和。 依次得出含二堆石子的６个子序列的合并方案 f〔１，２〕＝７ f〔２，２〕＝１０ f〔３ ，２〕＝１１ c〔１，２〕＝１ c〔２，２〕＝１ c〔３，２〕＝１ f〔４，２〕＝９ f〔５，２〕＝６ f〔６，２〕＝５ c〔４，２〕＝１ c〔５， ２〕＝１c〔６，２〕＝１ 含三堆石子的６(３ ４ ６ ５ ４ ２ )个子序列的合并方案 f〔１，３〕＝２０ f〔２，３〕＝２５f〔３，３〕＝２４ c〔１，３〕＝２ c〔２，３〕＝２ c〔３，３〕＝１
f〔４，３〕＝１７f〔５，３〕＝１４ f〔６，３〕＝１４ c〔４，３〕＝１ c〔５，３〕＝１ c〔６，３〕＝２ 含四堆石子的６(３ ４ ６ ５ ４ ２ )个子序列的合并方案 f〔１，４〕＝３６ f〔２，４〕＝３８f〔３，４〕＝３４ c〔１，４〕＝２ c〔２，４〕＝２ c〔３，４〕＝１ f〔４，４〕＝２８f〔５，４〕＝２６ f〔６，４〕＝２９ c〔４，４〕＝１ c〔５，４〕＝２ c〔６，４〕＝３ 含五堆石子的６(３ ４ ６ ５ ４ ２ )个子序列的合并方案 f〔１，５〕＝５１ f〔２，５〕＝４８f〔３，５〕＝４５
c〔１，５〕＝３ c〔２，５〕＝２ c〔３，５〕＝２ f〔４，５〕＝４１f〔５，５〕＝４３ f〔６，５〕＝４５ c〔４，５〕＝２ c〔５，５〕＝３ c〔６，５〕＝３ 含六堆石子的６(３ ４ ６ ５ ４ ２ )个子序列的合并方案 f〔１，６〕＝６１ f〔２，６〕＝６２f〔３，６〕＝６１ c〔１，６〕＝３ c〔２，６〕＝２ c〔３，６〕＝２ f〔４，６〕＝６１f〔５，６〕＝６１ f〔６，６〕＝６２ c〔４，６〕＝３ c〔５，６〕＝４ c〔６，６〕＝３ f〔１，６〕是 f〔１，６〕，ｆ〔２，６〕，??f〔６，６〕中的最小
值，表明最小得分和是由序列〔１，６〕经５次合并得出的。我们从这个序列出发， 按下述方法倒推合并过程： 由 c〔１，６〕＝３可知，第５次合并的两堆石子分别由子序列〔１，３〕 和子序列〔４，3〕经４次合并后得出。其中 c〔１，３〕＝２可知由子序列〔１， ３〕 合并成的一堆石子是由子序列〔１，２〕和第三堆合并而来的。而 c〔１， ２〕＝１，以表明了子序列〔１，２〕的合并方案是第１堆合并第２堆。 由此倒推回去，得出第１，第２次合并的方案，每次合并得分第一次合并 ３ ４ ６?? -&７ 第二次合并 ７ ６?? -&１３１３??
子序列〔１，３〕经２次合并后合并成１堆， ２次合并的得分和＝７＋ １３＝２０。
ｃ〔４，３〕＝１，可知由子序列〔４，３〕合并成的一堆石子是由第４ 堆和子序列〔５， ２〕合并而来的。而 c〔５，２〕＝１，又表明了子序列〔５，２〕的合并方案是第５堆合并第６堆。由此倒推回去，得出第３、第４次合并的方案 每次合并得分： 第三次合并 ??５４ ２ -&６ 第四次合并 ??５ ６-&１１ ??１１ 子序列〔４，３〕经２次合并后合并成１堆，２次合并的得分和＝６＋１ １＝１７。第五次合并是将最后两堆合并成１堆，该次合并的得分为２４。 显然，上述５次合并的得分总和为最小 ２０＋１７＋２４＝６１ 上述倒推过程，可由一个
print（〔子序列〕）的递归算法描述 procedure print （〔i，ｊ〕） begin if ｊ〈〉１then ｛继续倒推合并过程 begin print（〔i，c〔i，j〕〕；｛倒推子序列１的合并过程｝ print（〔i＋c〔i，j〕－１〕mod n＋１，j－c〔i，j〕） ｛倒推子序列２的合并过程｝ for K：＝１ to N do｛输出当前被合并的两堆石子｝ if （第 K 堆石子未从圈内去除） then begin if（K＝i）or（K＝X）then 置第 K 堆石子待合并标志 else
第 K堆石子未被合并； end；｛then｝ 第 i 堆石子数←第 i 堆石子数＋第 X 堆石子数； 将第 X 堆石子从圈内去除； end；｛then｝ end；｛print｝ 例如，调用 print（〔１，６〕）后的结果如下： print（〔１，６〕）⑤ ┌──────┴──────┐ print（〔１，３〕）② print（〔４， ３〕）④ ┌─────┴─────┐ ┌─────┴─────┐ print( 〔１， )① print( ２〕 〔3， ) 1〕 print( 〔4， ) print( 1〕
〔５， ２〕)③ ┌──────┴──────┐ ┌── ────┴──────┐ print（〔1,1〕） print（〔2,1〕） print
（〔5,1〕） print（〔6,1〕） （图 6.2-5） 其中回溯至 ① 显示 ３ ４６ ５ ４ ② 显示 ７ ６５ ４ ２ ③ 显示 １３ ５４ ２ ④ 显示 １３５ ６ ⑤ 显示 １３ １１ 注:调用print 过程后，应显示６堆石子的总数作为第５次合并的得分。 Program S TypeNode = Record{当前序列的合并方案} c : L{得分和} d : Byte{子序列 1 的堆数}E SumType = Array [1..100,1..100] of
L {sumtype[i,j]-子序列[i,j]的石子总数} Var List : Array [1..100,1..100]of N {list[i,j]-子序列[i,j]的合并方案} Date, Dt : Array [1..100] of I {Date[i]-第 i 堆石子数,Dt-暂存 Date}Sum : ^SumT{sum^[i,j]-指向子序列[i,j]的石子总数的指针} F : T{文件变量} Fn : S{文件名串} N,
i, j : I{N-石子堆数,i,j-循环变量} Procedure Print(i, j : Byte);{递归打印子序列[i,j]的合并过程} Var k, x : S{k-循环变量;x-子序列 2 中首堆石子的序号} Begin If j && 1 ThenBegin{继续倒推合并过程} Print(i, List[i,j].d);{倒推子序列 1 的合并过程} x := (i + List[i, j].d - 1) Mod N+ 1;{求子序列 2 中首堆石子的 序号}
Print(x,j - List[i, j].d);{倒推子序列 2 的合并过程} For k := 1 to N Do{输出当前合并第 i 堆,第 x 堆石子的方案} IfDate[k] & 0 Then Begin If (i= k)or(x=k)Then Write(F, - Date[k], ' ') ElseWrite(F, Date[k], ' ') E { Then } Writeln(F);{输出换行符}
Date[i] := Date[x] := End { Then E { Print
Date[i] + Date[x];{原第 i 堆和第 x 堆合并成第ｉ堆} - Date[x]{将原第 x 堆从圈内去除} } }
Procedure Main(s : Shortint); Var i, j, k : I t, x : L Begin Fori := 1 to N Do Begin{仅含一堆石子的序列不存在合并} List[i, 1].c := 0;List[i, 1].d := 0 E {For} For j := 2 to N Do{顺推含 2 堆,含 3 堆??含 N 堆石子的各子序列的 合并方案} For i := 1 to N Do Begin{当前考虑从第 i 堆数起,顺时针数
j 堆的子序列} If s = 1 Then List[i, j].c := Maxlongint{合并[i,j]子序列的 得分和初始化} Else List[i, j].c := 0; t:= Sum^[i, j];{最后一次合并的得分为[i,j]子序列的石子总数} For k := 1 to j - 1 Do Begin{子序列 1 的石子堆数依次考虑 1 堆??j-1 堆} x := (i+ k - 1) Mod N + 1;{求子序列 2 首堆序号}If (s=1) And (List[i,k].c
+ List[x,j-k].c+t & List[i, j].c) Or (s=2) And(List[i,k].c + List[x,j-k].c+t & List[i, j].c) { 若该合并方案为目前最佳,则记下} Then Begin List[i, j].c := List[i,k].c + List[x, j - k].c + List[i, j].d := k End { Then } End { For } E {For } {在子序列[1,N],[2,N],??,[N, N]中选择得分总和最小(或最大)的一
个子序列} k :=1; x := List[1, N].c; For i := 2 to N Do If (s = 1) And (List[i, N].c & x)Or (s = 2) And (List[i, N].c & x) Then Begin k := x := List[i, N].c E{ Then } Print(k, N);{由此出发,倒推合并过程} Writeln(F, Sum^[1, N]);{输出最后一次将石子合并成一堆的石子总数}
Writeln(F); Writeln(list[k, N].c) E { Main } Begin Write('File name = ');{输入文件名串} Readln(Fn); Assign(F, Fn);{该文件名串与文件变量连接}Reset(F);{文件读准备} Readln(F, N);{读入石子堆数} For i := 1 to N Do Read(F, Date[i]);{读入每堆石子数} New(Sum);{求每一个子序列的石子数 sum} For i := 1 to NDo Sum^[i,
1] := Date[i]; For j := 2 to N Do For i := 1 to N Do Sum^[i, j] :=Date[i] + Sum^[i Mod N + 1, j - 1]; Dt := D{暂存合并前的各堆石子,结构相同的变量可相互赋值} Close(F);{关闭输入文件} Assign(F, 'OUTPUT.TXT');{文件变量与输出文件名串连接}Rewrite(F);{文件写准备} Main(1);{求得分和最小的合并方案} Date := Dt;{恢复合并前的各堆石子}
Main(2);{求得分和最大的合并方案} Close(F){关闭输出文件} End.
#include &iostream& #include &set& #include &vector& #defineMAX 6 int dis[MAX][MAX]={ 0, 10, 20, 30, 40, 50, 12, 0,18, 30, 25, 21, 23, 19, 0, 5, 10, 15, 34, 32, 4, 0, 8, 16, 45, 27, 11,10, 0,18, 56, 22, 16,20, 12, 0
}; typedef struct {//当前所在的城市vector&int&//当前未访问的城市 set&int&//由于 set 自动排序，相同状态的 vector可能不同，但 set 必然相同//从当前城市到终点回到起点的距离 } /*测试用*/ void printVec(vector&status& vec) { vector&status&::vector&int&::iterator
for(iter=vec.begin();iter!=vec.end();iter++) {cout&&(*iter).curcity&&& &&;for(it=(*iter).unvisited.begin();it!=(*iter).unvisited.end();it++) {cout&&*it&&& &; } cout&&&&&&&&distance:&&&(*iter).distance&& } } //看看当前状态的城市中是否包括城市 i bool contain(int i,
status &sta) {vector&int&:: if(i==sta.curcity) else {for(iter=sta.unvisited.begin();iter!=sta.unvisited.end();iter++) if(i==*iter) } } /*合并相同状态*/vector&status& combine(vector&status& vec) { vector&status&new_
vector&status&:: while(vec.size()&0) {iter=vec.begin(); temp=* vec.erase(iter); for(;iter!=vec.end();iter++) {if((temp.curcity==(*iter).curcity)&&(temp.type==(*iter).type)) {if((*iter).distance&temp.distance) temp=* iter=vec.erase(iter);
iter--;} } new_vec.push_back(temp); } return new_ } int main() {vector&status& pre_ vector&status& cur_ //从后往前推，初始化 for(int i=1;i&MAX;i++) { sta.curcity=i;sta.distance=dis[i][0]; cur_vector.push_back(sta); } //依次递推，递推 MAX-2 次
for(int j=0;j&MAX-2;j++){pre_vector=cur_ cur_vector.clear(); for(int i=1;i&MAX;i++) {vector&status&::for(iter=pre_vector.begin();iter!=pre_vector.end();iter++)
{ status temp=* if(contain(i,temp)==false)//为确保状态中没有重复路径 { status new_stat= vector&int&::iteratorint_iter=new_stat.unvisited.begin();new_stat.unvisited.insert(int_iter,new_stat.curcity);//加入 vector new_stat.type.insert(new_stat.curcity);//加入 set new_stat.distance+=dis[i][new_stat.curcity];//计算距离
new_stat.curcity=i; cur_vector.push_back(new_stat); } } } //记录相同状态最短路径，并合并相同状态 cur_vector=combine(cur_vector); }//end for
//printVec(cur_vector);
//递推完毕后，最后一步，计算起点到每个状态的距离，找到最短路径vector&status&::iterator iter=cur_vector.begin(); status shortest=*int min_dis=shortest.distance+dis[0][shortest.curcity]; iter++;for(;iter!=cur_vector.end();iter++) { int temp_dis=dis[0][(*iter).curcity]+(*iter).if(temp_dis&min_dis)
{ min_dis=temp_ shortest=* } } //打印结果 vector&int&::iterator iter_ cout&&&minimumdistance is &&&min_dis&& cout&&&the shortestpath is &&&&1 &&&shortest.curcity+1;for(iter_city=shortest.unvisited.begin();iter_city!=shortest.unvisited.end();iter_city++)cout&&&
&&&*iter_city+1; cout&&&1&&& return 0;
剖分问题 2 多边形剖分
-----多边形剖分 有 N 个顶点（从 1 到 N 编号）的凸多边形，每个顶点的权均已知。问如何把这 个凸多边形划分成 N-2 个互不相交的三角形，使得这些三角形顶点的权的乘积之 和最小？
输入数据： 第一行 顶点数 N（N&50）。第二行 N 个顶点（从 1 到 N）的权值，权值为小于 32768 的整数。
输出数据： 第一行为各三角形顶点的权的乘积之和最小值。
Sample Input
division.in 5 121 122 123
Sample Output
division.out
由一个点射出的一条线可以把多边形分成左右两部分，那么就转化成了相同类 型的子问题。 该多边形的权值乘积之和最小值就等于左边部分的最小值与右边部分的最小值相加。
P.S.本来以为还得用高精度，结果刚才看了看原来写的程序发现 long long 完全可以搞定。
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]); i&k&j;
#include&iostream& #define MAX 50 int n,w[MAX]; longlong f[MAX][MAX]; void init() { cin&&n; for(i=1;i&=n;i++)cin&&w[i]; memset(f,0,sizeof(f)); } void solve() { int l,i,j,k; long longtemp,t1; for(l=2;l&=n;l++) for(i=1;i&n;i++) { j=i+l-1;for(k=i+1;k&j;k++)
{ t1=w[i]; t1*=w[j]; t1*=w[k]; temp=f[i][k];temp+=f[k][j]; temp+=t1;
if(f[i][j]==0||f[i][j]&temp) f[i][j]= } } } void print() {cout&&f[1][n]; } int main() { init(); solve(); print(); return 0; }
剖分问题 3 乘积最大
------乘积最大 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学 家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持 人给所有参加活动的选手出了这样一道题目：设有一个长度为 N 的数字串，要求选手使用 K 个乘号将它分成 K+1 个部分， 找出一种分法，使得这 K+1 个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当
N=3，K=1 时会有以下两种分法：1） 2） 3*12=36 31*2=62
这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。
【分析】设 f[i,j]表示前 j 个数划分成 i 段的最大乘积，w[i,j]表示第i 个数字到第 j 个数字的 数f[i,j]=max(f[i-1,j-1]*w[j,i]) (0&=k&=n)(1&j&=i&=n)
f[i,j]:=max(f[k,j-1]*mult[k,i]);
【源程序】 P Var f:array[0..31,1..40]a:t: n,k,i,j,h: function make(x,y:integer): vars:i: begin s:=0; for i:=x to y do s:=s*10+ord(a[i])-ord('0');exit(s); Begin fillchar(f,sizeof(f),0); readln(n,k);readln(a);
for i:=1 ton do f[0,i]:=make(1,i); for h:=1 to k do for i:=h to n do for j:=1 to i dobegin t:=f[h-1,j-1]*make(j,i); if t&f[h,i] then f[h,i]:=t; writeln(f[k,n]);End.
剖分问题 4 多边形-讨论的动态规划
-----多边形-讨论的动态规划
多角形是一个单人玩的游戏，开始时有一个 N 个顶点的多边形。如图，这里 N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从 1 编号到 N。第一步，一条边被拿走；随后各步包括如下： 选择一条边 E 和连接着 E 的两个顶点 V1 和 V2； 得到一个新的顶点，标记为 V1 与 V2 通过边 E 上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。
我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 。 用 f(i,j)表示从点 i 到点 j 进行删边操作所能得到的最大值，num(i)表示第 i 个顶点上的数，若为加法，那么：
f (i, j ) ? max ? ( f (k , i) ? f ( j ? k , i ? k )) 2 k ?1 f (i, i) ? num(i)
最后，我们允许顶点上出现负数。以前的方程还适不适 用呢？
-10 * 3 图六 + 2 * -5
- 7 1 + 5
这个例子的最优解应该是（3+2）*（-10）*（-5）=250，然而如果沿用以 前的方程，得出的解将是（（-10）*3+2）*（-5）=125。为什么？ 我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前 的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。对于加法，两个最优相加肯定最优，而对于乘法 求最大值： 正数×正数，如果两个都是最大值，则结果最大 正数×负数，正数最小，负数最大，则结果最大 负数×负数，如果两个都是最小值，则结果最大求最小值： 正数×正数，如果两个都是最小值，则结果最小
正数×负数，正数最大，负数最小，则结果最小 负数×负数，如果两个都是最大值，则结果最小我们引入函数 fmin 和 fmax 来解决这个问题。fmax(i,j) 表示从点 i 开始， 到但 j 为止进行删边操作所能得到的最大值，fmin(i,j) 表示最小值。 当 OP=‘+’ Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)}Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)} 当 OP=‘*’
?fmax(i, k ) * f max(k ? 1, j ) ?fmax(i, k ) * f min(k ? 1, j ) ? f max(i, j )? ? ?fmin(i, k ) * f max(k ? 1, j ) ?fmin(i, k ) * f min(k ? 1, j ) ?
?fmin(i, k ) * f min(k ? 1, j ) ?fmax(i, k ) * f min(k ? 1, j ) ? f min(i, j )? ? ?fmin(i, k ) * f max(k ? 1, j ) ?fmax(i, k ) * f max(k ? 1, j ) ?
初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(i)1&=i&=k=&j=n 空间复杂度:O(n2) 时间复杂度:先要枚举每一条边为 O(n)，然后动态规划为 O(n3 )，因此总为 O(n4)。F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j]; 负正 f[I,k]*g[k+1,j];} g 为 min
剖分问题 5 最大奖励
-----最大奖励
f:=max(f,f[j]+(sum[j]-sum)*i-t
剖分问题 6 小 H 的小屋
-----小 H 的小屋F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);
贪心的动态规划
贪心的动态规划 1 快餐问题
-----快餐问题
一、问题描述 Peter 最近在 R 市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由 A 个汉堡，B 个薯条和 C 个饮料组成。价格便宜。为了提高产量，Peter 从 著名的麦当劳公司引进了 N 条生产线。所有的生产线都可以生产汉堡，薯条和饮 料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮 料的单位生产时间又不同。这使得 Peter 很为难，不知道如何安排生产才能使一 天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单 起见，假设汉堡、薯条和饮料的日产量不超过
100 个。 输入： 输入文件共四行。 第一行为三个不超过 100 的正整数 A、 C 中间以一个空格分开。 B、 第三行为 3 个不超过 100 的正整数 p1,p2,p3 分别为汉堡， 薯条和饮料的单位生产耗 时。中间以一个空格分开。 第三行为 N(0&=0&=10)，第四行为 N 个不超过 10000 的 正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。
F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3} 输出: 每天套餐的最大产量。 分析 本题是一个非常典型的资源分配问题。 由于每条生产线的生产是相互独 立， 不互相影响的， 所以此题可以以生产线为阶段用动态规划求解。状态表 示： 用 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* 1 00 4 ), 优化 在本题中， 可以在动态 规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由 A, B,C 计算， 即 mi n｛1 00 di v A， 1 00 di v B， 1 00 di v 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 ] di v p1do for j : =0 to mi n(q1 , tot[i ] di v p1 ) do for k: =0 to (tot[i ] -p1 *j )di v p2 do for k: =0 to mi n(q2, (tot[i ] -p1 *j ) di v p2) do for j 1 : =0 toj do for
j 1 : = max(0, j -t[i ] di v p1 ) to mi n(j , tot[i -1 ] di v p1 ) dofor k1 : = 0 to k do for k1 : =max(0, k-(t[i ] -(j -j 1 ) *p1 ) di v p2) to min(k, (tot[i -1 ] -p1 *j 1 ) di v p2) do
贪心的动态规划 2(过河)
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙 很讨厌踩在这些石子上。 由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上 青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中 L 是桥的长度）。坐标为 0 的 点表示桥的起点，坐标为 L 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。 一次跳跃的距离是 S到 T 之间的任意正整数（包括 S,T）。当青蛙跳到或跳过坐标为 L 的点时， 就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L，青蛙跳跃的距离范围
S,T，桥上石子的位置。你的任务是确定青蛙要 想过河，最少需要踩到的石子数。
-----过河 f[i]=min{{f(i-k)} (not stone[i]) {f(i-k)}+1}(stone[i]); +贪心压缩状态
算法分析： 看到题目首先想到的是时间复杂度为 O(L)的递推算法。但是 L 的上限为 10^9，这种算法显然是不行的。
仔细思考，可以得到下面的结论： 存在 N0，当 n&N0 时，n 可以由若干 S 到 T 之间的正整数（包括 S,T）组成。 因此，将障碍点按升序排列，当两相邻障碍点之间距离较大时，可适当缩小两障碍点之间距离，但不影响最终结果。 根据上述结论，改进递推算法。由于障碍点之间距离大大缩减，算法的复杂度是可以承受的。 特别地，当 S=T 时需要单独处理。程序： const max=105; var a,a1:array[0..101] b:array[0..100]
c,d:array[0..10000] l,s,t,m,ans,low,i,j,k,temp:flag: f: begin assign(