题三 加分二叉树（2003）
【问题描述】
设一个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.
[点评]基本题。考查了二叉树的遍历和动态规划算法。难点在于要记录当前最大加分二叉树的根节点。疑点是最大加分二叉树的前序遍历序列可能不唯一。
第三题：统计单词个数（2001）
给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字符串以每行20个字母的方式输入，且保证每行一定20个）。要求将此字符串分成k份（1<k≤40），且每份中包含的单词个数加起来最大（每份中包含的单词可以重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，但是选用this之后就不能再选th）。
分析：
这一题应该算是一道比较原创的题目。注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置 的参数 表示以位置 的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词 。这样对于所有的不同 个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的 的值，这一部分的复杂度为O(wl2) 。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下：
这里有初值 为：
这个式子中， 表示把字串前 个字符分成 段时所形成的最多单词的数目， 表示字串的第 个字符开始的 个字符形成的字串中所能形成的单词数。这里 由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有 的 ，如果 存在（也就是有单词可以在位置 匹配上），且 ，则该位置必然可以匹配上一个单词。把所有这样位置的数目加起来就可以得到 的值了。这样算法的复杂度为O(kl3)。
但这里计算还有一个技巧，就是我们可以依次按照 增加， 增加， 增加的顺序计算 的值。这样在 由 增加到 的时候，由于在计算 所对应的 值时可以用
这个方程进行复杂度为O(1)的递推计算，故总复杂度可以降到O(kl2+wl2)。
这种被称作双重动态规划的方法，请读者自己好好体会。
数据：
输入 输出
1 2 1thisisappleisthistheoopbooktheisurrtoywe4isofthebook 8
2 4 4dfhfghgdfksgdflsdsdssdsdsddfsdffssddsfdfasasassasdsdsdsdsdsdsadadadasdsdsdsdssdd4dssddfdfdfsdsdjkjjk 13
3 10 4aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1aaaaa 193
4 10 4sdfsdsassdasdddsasddsdasdsasdsadasdasdsaassasaasadassadsaaddssasdasdasdssddsassaasdasdasdasdasddsadsdsadasdasdasadssdssaasssdasdsasdassdssaadsaddsasdasdsadsaasaadsadsasddsadsadsssaadsdsaasddsaadsdsasa6aasadsdasasd 125
5 10 4sdfsdsassdasdddsasddsdasddassdsaadaasdsaassasaasadassadsaaddssasdsaasdassddsassasaddssassasdsaasssdsdsasdasdsddasdasdssaasssdasdsasdassdssaasadsassdssassdsasssasasdsasdsasdsasdsssasdsasdsasdsassdasdsa6asddsaadsdassadsda 65
（2000）
题二 乘积最大 (22分)
问题描述:
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目:
设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串: 312，当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入：
程序的输入共有两行:
第一行共有2个自然数N,K (6<=N<=40，1<=K<=6)
第二行是一个长度为N的数字串。
输出:
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
样例:
输入
4 2
1231
输出
62
第二题：
很明显的动态规划。
令d[i,j,k]为第i个数字到第j个数字加k个乘号所能够达到的最大值。
状态转移方程是：
d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举t, 满足i<=t<=j-1)
注意到状态转移的时候总是使k减小（或不变）的，所以把k作为阶段来递推（节约空间）。
在每个状态中，l=j-i越来越小，所以从l=0递推到l=n
即：
for k:=1 to c do
for l:=0 to n do
for i:=1 to n do
递推d[i,j,k]
显然，用两个数组记录d[i,j,k]和d[i,j,k-1],就可以只用两维：d[i,j]
于是算法框架就是(请对照我的源程序)：
初始化d1[i,j]
for k:=1 to c do
begin
for l:=0 to n do
for i:=1 to n do
用d1[i,j](k-1阶段)递推d2[i,j]（k阶段）
d1:=d2; {节省空间，因为递推的时候只与上个阶段有关，故只保留相邻两个阶段}
end;
高精度乘法的方法我不是用的模拟手算的过程（这个大家会做吧），而用了类似
多项式乘法的方法，因为我觉得这种写法很好记！(大家仔细看看我的mul过程)
程序见附件。
题四 方格取数 (33分)
问题描述:
设有N*N的方格图(N<=8)，我们将其中的某些方格中填入正整数，而其他的方格中则放人数字0。如下图所示（见样例 ，黄色和蓝色分别为两次走的路线，其中绿色的格子为黄色和蓝色共同走过的）：
A
13 6
7
14
21 4
15
14
B
某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入:
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出:
只需输出一个整数，表示2条路径上取得的最大的和。
样例:
输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出
67
第四题：
有同学搜索第一个人，拣了以后第二个人用动态规划，一定能得最优解，但时间效率不大高。
有同学采用贪心，即用动态规划算出第一个人最大能拣的数，再在剩下的数中用动态规划。
反例如下：
1 9 1
0 0 0
1 9 1
第一次是：
1->9->9->1
第二次是：1
和是21
但显然可以两次把所有的数拣完(22)。
本题是典型的多维动态规划，很象IOI93的第四题,另一个算法是网络流，很象IOI97第一题，
这里我只分析前者。这道题目的简单之处是阶段很好划分（对角线），这种方法我就不介绍了，
因为很多地方都有介绍。这里讲一种怪一点的动态规划^_^
容易想到的思路是：
令d[x1,y1,x2,y2]表示甲在x1,y1,乙在x2,y2以后（包括取走(x1,y1)）的过程中可以获得的最大和。
则d[1,1,1,1]就是原问题的解。
但是是否能取数和另一个人是否事先已经到过该格子有关，我们需要设计一种走的方法，使得只根据x1,y1,
x2,y2就能判断一些关键的格子是否已经到达过。这样，问题才具有无后效性。
为此，我们把路线作如下处理：
1)当两个人路线有交叉的时候，改成等效的，不交叉的。
如下图，1代表第一个人，2代表第二个人。X代表相遇点。
X111
2 1
222X2
12
12
1X1
2X
变成：
X222
1 2
111X2
12
12
1X2
1X
反正让2走右边就行了。
2)现在1在第y1列，2在第y2列，让1和2分别向右走,到达yy1和yy2列，然后向下走一格
这样如果yy1 < y2,便是分别取走第y1~yy1,y2~yy2列数，否则路线有重复，就取走y1~yy2的数。
为了方便连续取数，我用了一个sum[x,y1,y2]的数组，就是第x行的y1~y2的数。
请看我的程序中的相应部分。
这样，所有的走法都可以转换成上述的，具有无后效性的结构了。
由于递推是从d[x1,y1,x2,y2]到d[x1+1,y1',x2+1,y2'],而总有x1=x2=x,所以可以把状态节省为：d[y1,y2]
而把x(当前行)作为阶段来递推：
for x:=n-1 downto 1 do
begin
for y1:=1 to n do
for y2:=y1 to n do
枚举y1'和y2'作为新的y1和y2,注意保证y1' >= y1, y2' >= y2(题目规定), y1' <= y2'(刚才的分析),递推d[y1,y2]
d1:=d2; {只记录相邻两个状态}
end;
边界是什么呢？当然是从第n列的值了，就是sum[n,y1,n](从y1取到n)
说了这么多，真不知道我说清楚了没有（ 好象是没有:-P ），如果有什么不明确的地方，请大家在论坛上提出来。
一句话，就是两个人一起，一行一行往下走，每一行可以一次向右走若干步，但是要保证2在1的右边。
注意最后输出的是d2[1,1]。如果输出d1[1,1],n=1会得到0。（为什么？自己想啊）
现在程序就不难写了吧。程序见附件：
测试数据见附件。
第一题 拦截导弹（28分）（1999）
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统
有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高
于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以
只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算
这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截
系统。
样例：
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6（最多能拦截的导弹数）
2（要拦截所有导弹最少要配备的系统数）
[分析]
有经验的选手一看第一个问就知道是经典的动态规划 - 最长不升子序列。
令d[k]为打中第k枚导弹以后，含第k枚导弹在内一共最多可以打k枚,则有状态转移方程：
d[k]= MAX {d[i]+1,1}
(i>k)and(d[i]<=d[k])
显然有d[n]=1，故从n逆推至d[1]即可,则 MAX{d[k]}为所求。
1<=k<=n
第二问显然要难一点，最直观的算法是贪心，但是反例也容易找到，如：
6 5 1 7 3 2
如果第一次打6 5 3 2,显然还要打两次，而最好的方案是6 5 1/7 3 2。
显然失败之处在于第一种方案为了多打3和2，把1和7隔断了，
但事实上把3和2留给第二套打
还不是一样！因为每个导弹都要打到，故我们应该把注意力放在“打到每一枚导弹”。
在上一个例子中，7是必须打到的，
因为它是最高的，所以必有一次拦截是以7开头的！！！
既然是必须，那么打7的同时顺便打一打其他的绝对不比不打差！那么打哪些呢？
下面说明：应该打后面导弹中最高的一个K。
先定义一个概念：把当前能打的最大高度叫做“能力”
理由如下：
对于K以后的导弹，绝对该打K，因为对于K以后的导弹，不打K时能打到的，打了K也能打到（K是最高的嘛！）,
K等于是“白打”，而对于7和K之间的导弹，打了任何一个就一定不能再打K了（K最高嘛！）反正中间的和
K不能一次打，先打不会比后打差！
类似的，下一个目标是K后面的最高的。
可以证明，该算法是正确的（从略），基础较好的同学也可以通过建立有向无环图来理解和证明这一算法。
程序见附件。
