信息学奥赛——树型动态规划的实例分析
全国青少年信息学奥林匹克联赛
树型动态规划的实例分析
一、什么是树型动态规划
顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：
1．根—>叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。
2．叶－>根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。
二、例题与解析
加分二叉树
【问题描述】
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree 及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2
4 5
[分析]很显然，本题适合用动态规划来解。如果用数组value[i,j]表示从节点i到节点j 所组成的二叉树的最大加分，则动态方程可以表示如下：
value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j], value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-
2]*value[j,j], value[j,j]+value[i,j-1]}
题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组root[i,j]表示
[PASCAL源程序]
{$N+}
program NOIP2003_3_Tree;
const
maxn=30;
var
i,j,n,d:byte;
a:array[1..maxn]of byte;
value:array[1..maxn,1..maxn]of comp;
root:array[1..maxn,1..maxn]of byte;
s,temp:comp;
f1,f2:text;fn1,fn2,fileNo:string;
procedure preorder(p1,p2:byte);{按前序遍历输出最大加分二叉树}
begin
if p2>=p1 then begin
write(f2,root[p1,p2],' ');
preorder(p1,root[p1,p2]-1);
preorder(root[p1,p2]+1,p2);
end;
end;
begin
write('Input fileNo:');readln(fileNo);
fn1:='tree.in'+fileNo;fn2:='tree.ou'+fileNo;
assign(f1,fn1);reset(f1);
assign(f2,fn2);rewrite(f2);
readln(f1,n);
for i:=1 to n do read(f1,a[i]);
close(f1);
fillchar(value,sizeof(value),0);
for i:=1 to n do begin
value[i,i]:=a[i];{计算单个节点构成的二叉树的加分}
root[i,i]:=i;{记录单个节点构成的二叉树的根节点}
end;
for i:=1 to n-1 do begin
value[i,i+1]:=a[i]+a[i+1];{计算相邻两个节点构成的二叉树的最大加分}
root[i,i+1]:=i;{记录相邻两个节点构成的二叉树的根节点；需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个；这里选编号小的为根节点，则编号大的为其右子树；若选编号大的为根节点，则编号小的为其左子树；因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。如果最大加分二叉树的所有节点的度数都是0或2，则最后输出的前序遍历结果是唯一的。}
end;
for d:=2 to n-1 do begin{依次计算间距为d的两个节点构成的二叉树的最大加分} for i:=1 to n-d do begin
s:=value[i,i]+value[i+1,i+d];{计算以i为根节点，以i+1至i+d间所有节点为右子树的二叉树的最大加分}
root[i,i+d]:=i; {记录根节点i}
for j:=1 to d do begin
temp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];{计算以i+j为根节点，以i至i+j-1间所有节点为左子树，以i+j+1至i+d间所有节点为右子树的二叉树的最大加分}
if temp>s then begin{如果此值为最大}
s:=temp;root[i,i+d]:=i+j;{记下新的最大值和新的根节点}
end;
end;
temp:=value[i,i+d-1]+value[i+d,i+d];{计算以i+d为根节点，以i至i+d-1间所有节点为左子树的二叉树的最大加分}
if temp>s then begin
s:=temp;root[i,i+d]:=i+d+1;
end;
value[i,i+d]:=s;
end;
end;
writeln(f2,value[1,n]:0:0);{输出最大加分}
preorder(1,n);{输出最大加分二叉树的前序遍历序列}
close(f2);
end.
[点评]基本题。考查了二叉树的遍历和动态规划算法。难点在于要记录当前最大加分二叉树的根节点。疑点是最大加分二叉树的前序遍历序列可能不唯一。
Ps：其实这题真正意义上来说还是一道普通的dp题目，但它批上了树的外表，所以都拿来作对比和讨论，解题报告出自湖北省水果湖高中伍先军写的第九届全国青少年信息学奥林匹克联赛（N0IP2003）复赛提高组解题报告。
Ural 1018 二*苹果树
题目
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的
树
2 5
\ /
3 4
\ /
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第1行2个数，N和Q(1<=Q<= N,1 N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。 输出格式 一个数，最多能留住的苹果的数量。 样例输入 5 2 1 3 1 1 4 10 2 3 20 3 5 20 样例输出 21 解析：因为题目一给出就是二叉的，所以很容易就可以写出方程： a(I,j):=max(a(i.left,k)+a(i.right,j-k)),0<=k<=j 源程序代码： 由于比较简单便不给完全的代码了。 Function treedp(x,y:longint):longint; Var I,j,k:longint; Begin J:=0; For I:=0 to y do begin k:=treedp(b[x].l,I)+treedp(b[x].r,y-I); if k>j then j:=k; end; treedp:=j; End; 选课 [问题描述] 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？ 输入： 第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150) 接下来的N行,第I+1行包含两个整数k i和s i, k i表示第I门课的直接先修课，s i表示第I门课的学分。若k i=0表示没有直接先修课（1<=k i<=N, 1<=s i<=20）。 输出： 只有一行，选M门课程的最大得分。 样例： 解析： 这题比苹果树多了一个步骤就是把一棵普通树转化为二叉树。 读入数据时把二叉树建好：第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。 F（x，y）：表示节点x取y门课得最高学分，则 F（x，y）＝max（f（x.l,k-1）+x.v+f(x.r,y-k)）k=0,1,..y f（x.l,k-1）+x.v(课程x的学分) :表示选了课程x,左孩子选k-1门课,共k门课。 f (x.r,y-k)表示右孩子只能选y-k门课。 标程中节点－1表示空节点，0是根节点，1—n是n门可选课程的节点. 思考:若本题加上选那些课程可得到这个最大学分,怎样修改程序？ 实现： 怎么实现，是在竞赛中的很重要的一个问题，如果你想ac了这道题目的话，你应该熟悉怎么把一棵树转化成二叉树，完后怎么用递规的思想来实现动态规划。所以坚实的基础是很重要的东西，如果没有了基础，什么都是空中楼阁。 程序中已经边读边把二叉树建立好了。 源程序代码： program bluewater; type tree=record l,r,k:longint; end; var s:string; i,j,k,l:longint; n,m:longint; a:array[0..200] of tree; b:array[-1..200,0..150] of integer; f:array[0..200] of longint; procedure treedp(x,y:longint); var i,j,k,l:longint; begin if b[x,y]>=0 then exit; treedp(a[x].r,y);{只有右子树的情况} j:=b[a[x].r,y]; for k:=1 to y do{左右子树都有的情况} begin treedp(a[x].l,k-1); treedp(a[x].r,y-k); i:=b[a[x].l,k-1]+b[a[x].r,y-k]+a[x].k; if i>j then j:=i; end; b[x,y]:=j; end; begin readln(s); assign(input,s);reset(input); readln(n,m); fillchar(f,sizeof(f),0); for i:=0 to n do begin a[i].l:=-1;a[i].r:=-1;a[i].k:=-1;end; {build tree} for i:=1 to n do begin readln(k,l); a[i].k:=l; if f[k]=0 then a[k].l:=i else a[f[k]].r:=i; f[k]:=i; end; {bianjie} for i:=-1 to n do for j:=-1 to m do if (i=-1) or (j=0) then b[i,j]:=0 else b[i,j]:=-1; treedp(a[0].l,m); {output} writeln(b[a[0].l,m]); end. Tju1053 技能树 Problem 玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。 只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是 需要耗费技能点数的。 有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为 效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。 Input 该题有多组测试数据。 每组测试数据第一行是一个整数n（1<=n<=20）,表示所有不同技能的总数。 接下来依次给出n个不同技能的详细情况。 每个技能描述包括5行。 第一行是该技能的名称。 第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任何的先修技能便能学习。 第3行是一个整数L（1<=L<=20），表示这项技能所能拥有的最高级别。 第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能点数（0级表示没有学习过）。 第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分，分数不 在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。 接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。这里不会出现非法情况。 Output 每组测试数据只需输出最佳分配方案所得的分数总和。 Sample Input 3 Freezing Arrow Ice Arrow 3 3 3 3 15 4 6 Ice Arrow Cold Arrow 2 4 3 10 17 Cold Arrow None 3 3 3 2 15 5 2 10 0 0 1 Sample Output 42 Source 浙江省2004组队赛第二试 解析：这题是选课的加强版，但并难不倒我们 还是把一棵树转换为二叉树，完后从子节点到根节点作一次dp，最后得到最优解由于和上题很相像就不写方程了。 源代码程序： program bluewater; type tree=record s,sf:string; l,r,m:longint; c:array[1..20] of longint; d:array[1..20] of longint; end; var i,j,k,l,m,n:longint; a:array[0..20] of tree; b:array[0..20] of longint; learn:array[0..20] of longint; f:array[0..20,0..8000] of longint; function treedp(x,y:longint):longint; var i,j,k,l,max,o,p,q:longint; begin if f[x,y]<>-1 then begin treedp:=f[x,y];exit;end; max:=treedp(a[x].r,y); {learn>0} if learn[x]>0 then begin for k:=0 to y do begin i:=treedp(a[x].l,k)+treedp(a[x].r,y-k); if i>max then max:=i; end; end; {learn=0} l:=0;p:=0;i:=0; for o:=1 to a[x].m do begin if o>learn[x] then begin l:=l+a[x].c[o];p:=p+a[x].d[o];end; for k:=0 to y-l do begin i:=treedp(a[x].l,k)+treedp(a[x].r,y-l-k)+p; if i>max then max:=i; end; end; f[x,y]:=max; treedp:=max; end; function find(x:string):longint; var i,j:longint; begin for i:=0 to n do if a[i].s=x then break; find:=i; end; begin while not(eof(input)) do begin {input} readln(n); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); a[0].s:='None'; for i:=1 to n do with a[i] do begin readln(s); readln(sf); readln(m); for j:=1 to m do read(c[j]);readln; for j:=1 to m do read(d[j]);readln; end; readln(m); if m>8000 then m:=8000; for i:=1 to n do read(learn[i]);readln; {build binary tree} for i:=1 to n do begin k:=find(a[i].sf); if b[k]=0 then begin b[k]:=i;a[k].l:=i;end else begin a[b[k]].r:=i;b[k]:=i;end; end; {bian jie} for i:=0 to 20 do for j:=0 to 8000 do f[i,j]:=-1; for i:=0 to 8000 do f[0,i]:=0; {main} writeln(treedp(a[0].l,m)); end; end. 战略游戏 Problem Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。 请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵. Input 第一行为一整数Ｍ，表示有Ｍ组测试数据 每组测试数据表示一棵树，描述如下： 第一行 N，表示树中结点的数目。 第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)。 接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。 对于一个n(0 Output 输出文件仅包含一个数，为所求的最少的士兵数目。 例如，对于如下图所示的树： 答案为1（只要一个士兵在结点1上）。 Sample Input 2 4 0 1 1 1 2 2 3 2 0 3 0 5 3 3 1 4 2 1 1 0 2 0 0 0 4 0 Sample Output 1 2 Source sgoi 分析：这题有2种做法，一种是比较简单但不是很严密的贪心，如果测试数据比较刁钻的话就不可能ac，而这题是一道比较典型的树型动态规划的题目，这题不但要考虑子节点对他的根节点的影响，而且每放一个士兵，士兵所在位置既影响他的子节点也影响了他的根节点。不过状态还是很容易来表示的，动规实现也不是很难，不过这在这些例题中也有了些“创新”了。而且这题不是一个对二叉树的dp，而是对一颗普通树的dp，所以更具代表性。 源程序代码： program bluewater; const maxn=1500; var i,j,k,l:longint; m,n,p,q:longint; a:array[0..maxn,0..maxn] of boolean; b:array[0..maxn] of longint; c:array[0..maxn] of boolean; function leaf(x:longint):boolean; var i,j:longint; t:boolean; begin t:=true; for i:=0 to n-1 do if a[x,i] then begin t:=false;break;end; leaf:=t; end; function treedp(x:longint):longint; var i,j,k,l:longint; begin j:=0;{add} k:=0;{leaf} l:=0;{not put not leaf} for i:=0 to n-1 do if (a[x,i]) and (x<>i) then if leaf(i) then inc(k) else begin j:=j+treedp(i); if not(c[i]) then inc(l); end; {puanduan} if (k>0) or (l>0) then begin c[x]:=true;treedp:=j+1;exit;end; if (j>0) and (l=0) then begin treedp:=j;exit;end; end; begin {input} readln(m); for p:=1 to m do begin fillchar(b,sizeof(b),0); fillchar(a,sizeof(a),false); fillchar(c,sizeof(c),false); readln(n); for i:=1 to n do begin read(k,l); for j:=1 to l do begin read(q); a[k,q]:=true; b[q]:=1; end; readln; end; {main} for i:=0 to n-1 do if b[i]=0 then break; fillchar(b,sizeof(b),0); if leaf(i) then writeln('1') else writeln(treedp(i)); end; end. Ural 1039 没有上司的晚会 背景 有个公司要举行一场晚会。 为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司（上司的上司，上司的上司的上司……都可以邀请）。 题目 每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。 输入格式 第1行一个整数N（1<=N<=6000）表示公司的人数。 接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。 接下来每行两个整数L，K。表示第K个人是第L个人的上司。 输入以0 0结束。 输出格式 一个数，最大的气氛值和。 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 样例输出 5 http://acm.timus.ru/submit.aspx?space=1&num=1039 分析： f[i,1]表示邀请i的最大值 f[i,2]表示不邀请i的最大值 f[i,1]=sigma(f[i.sons,2]) f[i,2]=sigma(max{f[i.sons,1],f[i.sons,2]}) 这个又是树型动态规划的一种分类，每个结点都有二种状态既选与不选。 动态规划专题（六）：树型动态规划 （重庆巴蜀中学黄新军） 信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘手的问题。这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此要用动态规划解决。 和一般动态规划问题一样，这类问题的解决要考虑如下三步： 1、确立状态：几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体问题考虑是否要加维，加几维，如何加维。 2、状态转移：状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分析的重点。 3、算法实现： 由于模型建立在树上，即为树型动态规划。 【例题1】二叉苹果树 【问题描述】 有一棵苹果树，如果树枝有分叉，一定是分2叉(就是说没有只有1个儿子的结点)，这棵树共有N个结点(叶子点或者树枝分叉点)，编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树： 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。 【文件输入】 第1行2个数，N和Q(1<=Q<=N,1 树型动态规划 补充二叉树的遍历的相关知识： 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进 行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树 中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处 理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3 种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。 先序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①访问根结点 ②先序遍历左子树 ③先序遍历右子树 先序遍历右图结果为：124753689 中序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①中序遍历左子树 ②访问根结点 ③中序遍历右子树 中序遍历右图结果为：742513869 后序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①后序遍历左子树 ②后序遍历右子树 ③访问根结点 后序遍历右图结果为：745289631 满二叉树： 一棵深度为h且有 2^h-1个结点的二叉树。 满二叉树一定为完全二叉树，但是完全二叉树不一定为满二叉树。 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 满二叉树有如下性质： 如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h; 1、它的叶子数是：2^(h-1) 2、第k层的结点数是：2^(k-1) 3、总结点数是：2^k-1 (2的k次方减一) 4、总节点数一定是奇数。 完全二叉树： 若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。 1、二叉树的序遍历 题目描述Description 求一棵二叉树的前序遍历，中序遍历和后序遍历 输入描述Input Description 第一行一个整数n，表示这棵树的节点个数。 接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。 输出描述Output Description 输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。 样例输入Sample Input 5 2 3 4 5 0 0 0 0 0 0 样例输出Sample Output 1 2 4 5 3 4 2 5 1 3 4 5 2 3 1 #include 最优二叉查找树 【源程序】 //本程序测试用例为课本例题 #include } return C[1][n]; } int main() { int n; double p[100]; printf("请输入字符个数："); scanf("%d",&n); printf("\n"); printf("请输入每个字符的查找概率："); for(inti=0; i 动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出: 对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0. 样例输入: 样例输出： 动态规划算法研究与应用 1.引言 动态规划被认为是组成运筹学其中的一部分，也被当成为进行运算决定时最好的一种数学方式。在1950年左右，美国相关方面的几位数学家，对阶段决策期间关于优化的问题做了大量的研究，并发布著名的最优化理论，将众多的阶段变成了一个一个单一的问题，并分别进行解答，最后，发明了能够处理这种相关优化方面事情新的解决措施——动态规划。到了1957年，创造出了Dynamic Programming这一名著，被称为该领域创作第一人[1]。 在数学和计算机科学领域，动态规划算法对于求解最优解的问题方便快捷。动态规划方法经常用来解决生活中的实际问题，这些问题往往可以分解为很多个子问题，每个子问题都有一个对应解，其中的临界值就是我们所要求得的最优解。动态规划并非一种数学算法，而是用于最优化解题的一种技巧和方法。它非但不具有一个标准的数学方程式，不能够推导出清晰明确的解题步骤，更不具备万能性。对于要解决的若干问题，一定要建立在正确理解的基础上具体问题具体分析，用我们现有的数学知识和丰富的想象力创建模型，结合日常的技巧分析求解。客观人为的介入时间和空间因素，只要可以分为若干子问题的多状态过程，就可以用此方法快速求解。 2.动态规划算法简介 动态规划诞生之后，很快就在在工业生产、金融管理、工程技术、和资源最大化利用等领域得到了好评。在处理路线规划、物品进出库管理、资源最优化利用、更换设备、顺序、装载等问题，动态规划算法相比于其他算法更有优势而且更加便捷。 2.1基本原理 其主要的理论可以被理解成是将求解的划分成若干个子问题，并将其称作为N，然后这些子问题又有N个解的情况，其中这些可行解之中一定会有一个最优解，研究动态规划也就是希望能够找到最优解[2]。 如何能够合理的推导出基本的最优化方程式和找出唯一的临界值是研究动 动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么 2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配 资金，使总效益值最大？## 表8－47 解：设S－A,B,C项目的总投资额，S－B、C项目的总投资额21S－C 项目的投资额；3X－k项目的投资额；k（X－A项目的投资额，X －B项目的投资额，X－C项目的投资额）312W（S,X）－对K项目投资X后的收益：W（S,X）＝W (X) kkkkkkkkk T (S,X)－S=S-X k k+1kkkk f (S)－当K至第3项目允许的投资额为S时所能获得的最大收益。kkk为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S＝0，建立递归方程4f(S)=0 k4 f (S)=max{ W (X)+f(S)} k=3,2,1 k+1kk +1kkk X∈D(S) kkk第一步，K=3 f(S)=0 44 f (S)=max{W (X)+f (S)} 434333X∈D(S) 333S=S-X3 34 第二步：)} f (S (X (S)=max{W)+f K=2 322322) X ∈D(S 222-X =S S232 W (X)+f (S-X) 22322 第三步：)} (S (X) =max f (S {W)+ f K=1 211121) D X∈(S111- X S= S 1 21 ) (X- X)+ f (SW1 12 11 S=4 →S=1 →S=1 312↓↓ ↓ X*=3 X*=0 X*=1 312百万。1投资C 不投资B 百万，3投资A． 总收益164百万元。 3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？ 浅谈室内区域活动规则的建立 室内区域活动是教师根据幼儿的发展现状和发展目标,创设多种领域的学习区域。提供活动材料,让幼儿通过自身的摆弄、操作去感知、思考、寻找问题的答案。而教师的任务是关注幼儿在活动中的表现和反应,敏感的察觉他们的需要,及时以适当的方式应答,形成合作探究式的师生互动。 我国著名学前教育家陈鹤琴先生曾说过:“小孩子是生来好动的,是以游戏为生命的”。孩子们就是在游戏中、在玩中一天天长大和进步的。如何使游戏真正成为孩子们自己的游戏,如何在游戏中最大限度的发挥孩子们的主观能动性,他们玩什么,怎样玩,玩多久等等,这就需要我们放开手,给予他们自由发挥潜能的机会。 爱玩游戏是每个孩子的天性,游戏一直以他独特的魅力吸引着无数的孩子。人们对游戏的认识越来越深入。而区角活动作为一种教育游戏活动,同样受到了孩子们的普遍欢迎。它重在创设一种宽松、和谐的环境,提供丰富的材料,以及选择广泛的内容。而教师在此过程中只是一个观察者,引导者。因此,孩子们学的特别轻松、自然、没有压力,他们可以做自己想做的事。这种个别化的教育形式尊重了幼儿的个体差异,满足了幼儿个体发展的需要。 都说“没有规矩,不成方圆”就像象棋里的楚河汉界,马路上的红绿灯,都是规则,幼儿园区域活动也都应有合适的规则,这样才能给幼儿充分自主活动的机会,帮助他们有计划、有目的、守规则地进行区域游戏,才好让游戏进行得更加顺畅。 一、规则包含的内容 1、人数的规定 幼儿园活动空间小,各个区域提供的材料比较有限,也有幼儿兴趣不同,所以对每个活动区角规定人数是很有必要的。它提示幼儿关注游戏开展的情况,也能培养孩子的协商能力。 我班在设计区域游戏人数时,每个人都有一个写着自己的名字的小钥匙,在各个区域明显的位置贴好对应数的口袋,当幼儿听到音乐时把自己的小钥匙插到 各区的口袋里,只要幼儿拿好进区卡插满进区标志后,后面的幼儿就要选择其它的区域进行游戏。比如,我班的“美食城”为幼儿提供了许多的富有天津特产的小吃,十八街麻花、煎饼果子、狗不理包子、龙嘴茶汤、传统火锅。这个角色区一直是孩子们的最爱。平时活跃的、内向的,每到区域开始,都争先恐后地去插卡,每次都很拥挤,但是看到区域卡插满了,就知道去别的区域玩了。 2、游戏的玩法 每个区域的游戏玩法,我们都可以在规则中告诉幼儿,小班时我们大都采用图画的方式告诉幼儿;中班采用了用图文并茂的形式,但还是文字比较多,幼儿还不太看得懂,所以我们也就采用照片的形式,将幼儿在玩的过程将照片拍下来,在规则区展示,这样孩子们就更加容易理解了。如中班上学期的时候,我们在益智区提供了系鞋带,现在的孩子都不会系鞋带,在这个区域的规则中,我们一个老师在示范,另外一个老师就将步骤拍下来展示在区域规则区。那天,班上的赵朗琪小朋友去益智区玩,她拿起了鞋面,就系鞋带,可是总也弄不好,这时张佳茵小朋友过来了,看了一会儿,她发现规则区的照片,就拉着赵朗琪的手说:“我们一起去看那边的照片。”说着,两个人就看着照片一起“研究”起来,终于在区域游戏时间快到的时候,两个人兴高采烈的过来告诉我说:“老师,我们会系鞋带了。我们两个看着照片做的。”通过这个案例,我发现,提供给孩子直观的游戏玩法,还是很有用的。 3、游戏中应注意的事项 我觉得规则中应该提醒幼儿该注意的事项,这也是非常重要的,每个区域都会有不同的注意内容,如阅读区我们会让孩子要注意安静看书,不破坏书,一页一页翻书;在美工区,我们会让孩子注意,使用剪刀时不剪到手,纸屑要放入垃圾桶,不能扔地上等等。有一次,我们玩区域活动,孩子们玩的很尽兴,音乐一响,每个孩子都在忙碌,忙着收拾自己在区域的材料,收完后孩子们都回到了位置,等待老师的评价,当我 第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。 浅谈幼儿园区域活动规则的探索 姓名：胡君教龄:17年职务:年级组长地址: 江苏省无锡市长安街道新惠幼儿园 邮编:214174 电话号码:83562280 摘要： 区域活动是一种人为创设自然情景下的幼儿自愿、自发的游戏，是我们现在普遍采取的一种教育活动形式。在幼儿园里要有序有质量的开展好区域活动，那首先就要制定出有效的规则：1、在讨论中共同商讨2、在试误中逐步形成3、在活动前明确规定。另外是区域活动规则的遵守，我们可以运用以下三种方法来更好的帮助幼儿来掌握：1、暗示法。2、图示法。3、提醒法。 区域活动是一种人为创设自然情景下的幼儿自愿、自发的游戏，是我们现在普遍采取的一种教育活动形式。区域活动以其个别化的教育形式尊重了幼儿的个体差异，满足了幼儿个体发展的需要，成为幼儿园所喜欢的活动形式，也是当前幼儿园落实《幼儿园教育指导纲要》所指出的幼儿园教育应为幼儿“提供自由活动的机会，支持幼儿自主地选择、计划活动。”“为每个幼儿提供表现自己长处和获得成功的机会，增强其自尊心和自信心。”的最有效的措施。而区域活动所具有的自选性、自主性、小组活动，教育价值依托于操作材料、情境和相应的活动中的特点，决定了教师对区域活动的指导更多的只能是以间接的方式来进行。再加之，区域活动的规则所承载的独有的教育价值，如可以有机地将教育者的教育意图渗透其中；可以活动中起着组织、约束、调整幼儿活动行为和相互关系，最大限度地保证幼儿的活动权利等方面的作用，使得我们清楚地意识到，抓好区域活动规则的建设工作，是保证区域活动有效地开展的重要前提。 那么在区域活动中，如何帮助幼儿建立起适宜有效的规则，并让幼儿在活动中自觉地遵守呢？通过多年的实践，下面就此问题浅淡几点个人的看法。 一、区域活动规则的制订 区域活动既是幼儿的一种学习活动形式，同时也是教师所组织的一种教育活动形式。因而，区域活动规则的制订应该是由教师和幼儿来共同完成，偏废某一方都是不妥的。在实践中，我们慢慢的总结出师幼共同制订活动规则的三种比较有效的方法： 1、在讨论中共同商讨 讨论往往是围绕在区域活动中所遇到的带有普遍性的“问题”而展开的，这种“问题”一般是会影响到该活动正常进行，又是幼儿无法自行解决的。讨论的目的就是要建立起相应的规则来解决当前所面临的“问题”。如，有些区域因人数较多，而发生了幼 动态规划 装箱问题（01背包）： 有一个箱子容量为VV（正整数，0≤V≤20000），同时有n个物品（0 完全背包的模板题面是这样的：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以无限选取)，使其重量的和小于等于M，而价值的和为最大。 完全背包 [无限量]的采摘药输入： 70 3 71 100 69 1 1 2 输出：140 每个数组在满足条件，可以遍历多次 01背包 实现代码：采药-传送门 输入： 70 3 71 100 69 1 1 2 输出：3 每个数组遍历一遍 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第jj件物品的价格为v_[j]，重要度为w_[j]，共选中了k件物品，编号依次为j_1,j_2,…,j_k，则所求的总和为： w_[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。 谈对系统工程的认识 摘要：随着社会经济发展和科学的进步，人类社会出现了越来越多的大型复杂的系统。这些系统的规划建造及运用都要建立在科学的基础之上，系统工程作为对系统的进行组织管理的技术便由此而产生。 1.1引言 “系统”这个名词，这个词在拉丁语中，是“在一起”“放置”的意思，因此，很久以来，他都是表示群体集合的概念的。但作为一个科学概念，还是在20世纪以来由于科学发展和人类文化的累积才是他的内涵逐步明确起来。他作为一门现代化的学科，还是从20世纪40年代开始的，是由美国贝尔电话公司在发展微波通信网时，首先提出的“系统工程”这个名词，并提出了工程按系统思想分成阶段进行工作的一套工作方式。后来，由于二战的需要，为了把整个军事系统的行动从科学上加以研究，便形成了运筹学这门学科，并且起到了很大的作用。战后，人们把它应用到经营管理方面，也起到了重要的作用，使它成为系统工程的一个有力基础。在1957年，第一本《系统工程》专著出版，标志这这门学科正式产生。 现在，系统工程已经有了长远的发展，他的思想和方法来自不同的行业和领域，又吸收了不同的邻近学科理论，所以造成了系统工程上定义的多样性，但从实用性上来说，他方法性的应用工程学科，它跨越了各个学科领域的横断性学科，从整体，全局的方向去考虑解决问题，同时，他不仅涉及到技术方面，还用在了难以精确描述上的社会，心理因素上，因此，可以说，它是一门总揽全局，着眼整体，从不同视角和不同方法来处理的系统中的各个部分，来规划和设计组建运行整个系统，是系统中的技术经济社会效果达到最优的方法性学科。 虽然说他是不可界定的，当然不妨碍我们去掌握和追随他的思想，发展他的细想。 2谈对线性规划问题的认识 2.1线性规划解释含义 前面谈到系统分析，在进行系统分析时，我们总要用所研究的系统进性描述，而线性规划，就是我们在描述系统中我们所用到的一种系统分析语言。 它是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法，它所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素. 它的数学模型的一般形式是（1）列出约束条件及目标函数（2）画出约束条件所表示的可行域（3）在可行域内求目标函数的最优解 2.2线性规划问题及其数学模型 一问题的提出 例1 某工厂在计划期内要安排生产甲乙两种产品，已知条件如下，如何安排计划可 树形动规题型分析北京大学李煜东 Ural1039 没有上司的舞会 题目大意：Ural大学有N个职员，编号为1~N。他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。 F[i][0]表示以i为根的子树，i不参加舞会时的最大快乐指数。 F i0= s∈Son i Max(F s0,F[s][1]) F[i][1]表示以i为根的子树，i参加舞会时的最大快乐指数。 F i1=Happy i+ s∈Son i F s0 通过DFS求出F数组，目标就是Max(F[1][0],F[1][1])。 Nescafé8 创世纪 题目大意：上帝手中有着N(N<=1000000)种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去建造世界。每种世界元素都可以限制另外一种世界元素，上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它。 上帝希望知道他最多可以投放多少种世界元素？ 每个世界元素的出度都是1(只能限制另外一种)，所以题目中的限制条件构成内向树森林。 如果题目中的限制条件构成的图是一棵树，那么DP方法和上一题类似：F[i][0]表示i没有被投放时，以i为根的子树里最多可以投放多少种世界元素。 F[i][1]表示i被投放时，以i为根的子树里最多可以投放多少种世界元素。 F i0=s∈Son i Max(F s0,F[s][1]) F i1=Max F s0+s′∈Son i,s′≠s Max F s′0,F s′1|s∈Son i 如果是内向树，那么任意枚举基环上的一条边，先把它断开(不使用这个限制条件)，在剩余的树上进行树状动规；然后再强制使用这个限制条件，再进行一次树状动规。 1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0 2、最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 3、括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2 动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 动态规划专题分类视图数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。 【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣 【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示 (A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。 【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不 《运筹学》课程 专题论文 论文题目：浅谈不同方法在物流中心选址问题中的 应用比较 专 业： 信息与计算科学 班 级：一班 组 长：李春梅 完成人姓名及学号： 2009 年 6 月 29 日 论文评价指标与鉴定意见 浅谈不同方法在物流中心选址问题中的应用比较专业：信息与计算科学姓名：李春梅崔建青吴丹青杨木兰李斯谢欢 摘要本文指出三种选址模型即双层规划模型，动态规划模型和模糊评判模型在物流中心选址问题中的应用，从而从许多可用的选址方案中挑选出最佳选址方案。最后,通过一个具体的实例,阐述了如何解决实际的选址问题。 关键词物流中心选址双层规划动态规划模糊评判 Different methods of logistics center location Problem in the application of relatively Specialty：Information and Computing Science Name：lichunmei cuijianqing wudanqing yangmulan lisi xiehuan ABSTRACT This article pointed out that the three site selection models that are, bi-level programming model, dynamic programming model and the fuzzy evaluation model in the logistics center location problem in the application site from a number of programs available to select the best location of the program. Finally, we use a specific example on how to resolve the issue of the actual site. Key Words:Logistics center Location Bi-level programming Dynamic programming Fuzzy evaluation 1.加分二叉树(binary.c/cpp) NOIP2003提高组第3题 【问题描述】 设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历 【输入格式】 第1行：一个整数n（n＜30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。 【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5 F(I,j) I,i+1…..j 枚举K（根结点） F(I,j)=max{d[k]+f[I,K-1]*f[K+1,j]} 1…I K…..j…..n F(I,i)=d[k] F(1,n)\ 边界：空树和只含有一个结点的树 自底向上递归前序遍历（根－左－右）二维数组记录决策 时间复杂度：I j K N3 30*30*30=27000 最高加分：4*109 int 2.1*109long float double(双精度)动态规划专题(六)：树型动态规划
树型动态规划(C++版)
最优二叉查找树_动态规划
动态规划练习试题和解答
浅谈我国动态规划算法研究与应用
动态规划讲解大全(含例题及答案)
动态规划习题答案
论文—浅谈室内区域活动规则的建立
动态规划习题
浅谈幼儿园区域活动规则的探索
动态规划试题
浅谈对系统工程的认识
树形动规题型分析
动态规划典型例题
动态规划习题完整版
动态规划论文
试题(树型动规)