经典算法普及——基础篇

kon3155

【能量项链】
    在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。
    需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
    例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【输入文件】
    输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
    至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
【输出文件】
输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。
【输入样例】
4
2 3 5 10
【输出样例】
710

【参考答案】

【网上解题思路】
    简单的说：给你一项链，项链上有n颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？
　　我们用top表示第i颗珠子的头标记，用wei表示第i颗珠子的尾标记，合并两颗相邻珠子所释放的能量是：
　　Q=top*wei*wei[i+1]或top*top[i+1]*wei[i+1]; （一个样的）
　　合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。
　　n个珠子进行一次合并的后，就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
　　既然是dp题目，必然要满足dp的两大条件：、
　　1.最优子结构性质；
　　设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
　　证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。
　　　　　　 那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾。
　　最优子结构性质得证。
　　 2.无后效性；
　　 无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。
　　
　　算法已经定了下来了，关键是怎么实现了。
　　项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的maxQ[1,n]也就不同的。所以我们要对这些maxQ[1,n]进行打擂，取其最大的一个，即为解了。
　　dp的转移方程是：
　　 Best=maxQ[1,n] 1<=i<=n (i表示从第i颗珠子处展开，顺次标号）；
　　 Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=n };
　　 其中Q[i,i]=0 1<=i<=n;
　　dp的时间复杂度为O(n^3)，n种的展开方法对应需要n次的dp，所以时间复杂度为O(n^4)。空间为O(n^2)。
　　显然O(n^4)过这个题目是有点欠缺的，对的大的数据貌似很容易超时的。
　　如果仔细想想，我们还是做了很不重复的工作的，不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间，既然展开做了很多的重复的工作，那么就合并起来吧。回到起点，开始的时候为什么我们要对项链做n次的展开呢，基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性，我们做如下处理：
　　　　a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1]　
　　　　　　　　　　　　（原来的）　　　　　 （延伸的）

　　也就是：
　　　　a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m]　　　
　　显然m=2n-1;
　我们对这一串珠子dp一次即可得解；dp方程为：
　　　Best=max{Q[i,i+n-1] 1<=i<=n}
　　 　Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k<j<=min(i+n-1,m)}
　　其中Q[i,i]=0 1<=i<=m;
　　显然时间复杂度为O(n^3)，空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。

kon3155

【0/1背包问题】
    在0/1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示选取物品i) 取得最大值。
【输入文件】
第一行一个数c，为背包容量。
第二行一个数n，为物品数量
第三行n个数，以空格间隔，为n个物品的重量
第四行n个数，以空格间隔，为n个物品的价值
【输出文件】
能取得的最大价值。
【分析】
    初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到最优解，看以下实例：
    贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c =105。当利用价值贪婪准则时，获得的解为x= [1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。
    贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
    贪心准则3：价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可 装入包的pi /wi 值最大的物品，但是这种策略也不能保证得到最优解。利用此策略解 n=3 ,w=[20,15,15], p=[40,25,25], c=30 时的得到的就不是最优解。  
    由此我们知道无法使用贪心算法来解此类问题。我们采用如下思路：
    在该问题中需要决定x1 .. xn的值。假设按i = 1，2，...，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r={c，c-w1} 为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案。也就是说在此问题中，最优决策序列由最优决策子序列组成。
    假设f (i,j) 表示剩余容量为j，剩余物品为i，i + 1，...，n 时的最优解的值，即：利用最优序列由最优子序列构成的结论，可得到f 的递归式为：
　 当j≥wi时：　f(i,j)=max{f(i+1,j),f(i+1,j-wi)+pi}
    当0≤j<wi时：f(i,j)=f(i+1,j)
    这是一个递归的算法，其时间效率较低，为指数级。

    考虑用动态规划的方法来解决:
    阶段：在前i件物品中，选取若干件物品放入背包中；
    状态：在前i件物品中，选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值；
    决策：第i件物品放或者不放；
    由此可以写出动态转移方程：
    用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
              f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}
这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f[n,c]

    算法框架如下：

1. 
   
2.    for i:=0 to c do    {i=0也就是没有物品时清零}
   
3.      f[0,i]:=0;
   
4.    for i:=1 to n do    {枚举n件物品}
   
5.      for j:=0 to c do  {枚举所有的装入情况}
   
6.       begin
   
7.        f[i,j]:=f[i-1,j];  {先让本次装入结果等于上次结果}
   
8.        if (j>=w[i]) and (f[i-1,j-w[i]]+p[i]>f[i,j])   {如果能装第i件物品}
   
9.          then f[i,j]:=f[i-1,j-w[i]]+p[i];             {且装入后价值变大则装入}  
   
10.       end;
    
11.    writeln(f[n,c]);
    

复制代码

为了进一步说明算法的执行原理，下面给出一个实例：
【输入文件】
10
4
5 1 4 3
40 10 25 30
【输出结果】下面列出所有的f[i,j]
0  0  0  0 40 40 40 40 40 40
10 10 10 10 40 50 50 50 50 50
10 10 10 25 40 50 50 50 65 75
10 10 30 40 40 50 55 70 80 80
从以上的数据中我们可以清晰地看到每一次的枚举结果，每一行都表示一个阶段。

kon3155

【开心的金明】
    金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入的第1 行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱数，m(<25)为希望购买物品的个数。）
从第2 行到第m+1 行，第j 行给出了编号为j-1的物品的基本数据，每行有2 个非负整数
v p
（其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5））

【输出文件】
输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2

【输出样例】
3900

【分析】
    典型的0/1背包问题，把总钱数N元当作背包容量，物品价格当作重量，重要度和价格的乘积当成参考价值，就可直接套用背包问题动态规划程序求解。
【参考答案】

kon3155

【金明的预算方案】
    金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过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]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。
【输入文件】
    输入文件的第1行，为两个正整数，用一个空格隔开： N m 其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）
    从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q （其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）
【输出文件】
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （<200000）。

【输入样例】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

【输出样例】
2200
【分析】
    简单方案：
    对每一个物品做两种决策，取与不取。如果取，满足两个条件：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;
    注意题目中还有一个条件：“每件物品都是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];}
    这种方法的DP效率大大提高，不过需要对输入数据进行重新处理，使之按属类重新编号。
【参考答案】

[ 本帖最后由 kon3155 于 2009-2-25 15:28 编辑 ]

kon3155

【加分二叉树】
    设一个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]表示

【参考答案】

kon3155

【字串编辑距离】
    设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。

【输入格式】
输入的第一行是字符串A，文件的第二行是字符串B。

【输出格式】
程序运行结束时，将编辑距离d(A,B)输出。

【样例输入】
fxpimu
xwrs
【样例输出】
5

【参考解答】
////////////////////
Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance
编辑距离
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。
1. 把某个字符ch1变成ch2
2. 删除某个字符
3. 插入某个字符
例如 s1 = “12433” 和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质:
1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1;
2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 ,
d(s1+ch1,s2),
d(s1,s2+ch2) );
第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1. 把ch1变成ch2
2. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))
3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2))
_3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )
可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的。
分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

1. 
   
2. 动态规划求解
   
3. 首先为了避免重复计算子问题，添加两个辅助数组。
   
4. 一. 保存子问题结果。
   
5. M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
   
6. 二. 保存字符之间的编辑距离.
   
7. E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
   
8. 三. 新的计算表达式
   
9. 根据性质1得到
   
10. M[ 0,0] = 0;
    
11. M[ s1i, 0 ] = |s1i|;
    
12. M[ 0, s2j ] = |s2j|;
    
13. 根据性质2得到
    
14. M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
    
15. m[i, j-1] ,
    
16. m[i-1, j] );
    
17. 复杂度
    
18. 从新的计算式看出，计算过程为
    
19. i=1 -> |s1|
    
20. j=1 -> |s2|
    
21. M[i][j] = ……
    
22. 因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)
    
23. 
    
24. #include <stdio.h>
    
25. #include <stdlib.h>
    
26. #include <string.h>
    
27. 
    
28. int _Min(int a,int b,int c)
    
29. {
    
30. int min=a;
    
31. if (b <min)
    
32. min=b;
    
33. if(c <min)
    
34. min=c;
    
35. return min;
    
36. }
    
37. 
    
38. int ComputeDistance(char s[],char t[])
    
39. {
    
40. int n = strlen(s);
    
41. 
    
42. int m = strlen(t);
    
43. 
    
44. //int d[][] = new int[n + 1, m + 1]; // matrix
    
45. int **d = (int **)malloc((n+1) * sizeof(int *));
    
46. for(int i=0; i<=n; ++i)
    
47. {
    
48. d[i] = (int *)malloc((m+1) * sizeof(int));
    
49. }
    
50. // Step 1
    
51. if (n == 0)
    
52. {
    
53. return m;
    
54. }
    
55. 
    
56. if (m == 0)
    
57. {
    
58. return n;
    
59. }
    
60. 
    
61. // Step 2
    
62. for (int i = 0; i <= n; i++)
    
63. {
    
64. d[i][0] =i;
    
65. }
    
66. 
    
67. for (int j = 0; j <= m; d[0][j] = j++)
    
68. {
    
69. d[0][j] =j;
    
70. }
    
71. 
    
72. // Step 3
    
73. for (int i = 1; i <= n; i++)
    
74. {
    
75. //Step 4
    
76. for (int j = 1; j <= m; j++)
    
77. {
    
78. // Step 5
    
79. int cost = (t[j-1] == s[i-1]) ? 0 : 1;
    
80. 
    
81. // Step 6
    
82. d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
    
83. }
    
84. }
    
85. // Step 7
    
86. return d[n][m];
    
87. }
    
88. 
    
89. int main(int argc, char *argv[])
    
90. {
    
91. char a[9999];
    
92. char b[9999];
    
93. printf("请输入字符串1\n");
    
94. scanf("%s",&a);
    
95. printf("请输入字符串2\n");
    
96. scanf("%s",&b);
    
97. int result= ComputeDistance(a,b);
    
98. printf("%d\n",result);
    
99. system("PAUSE");
    
100. return 0;
     
101. }
     
102. 
     
103. 
     
104. 
     
105. 
     

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 15:27 编辑 ]

kon3155

【花瓶插花】
    你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时至少有同样数量的花瓶。它们被按顺序排成一排，花瓶的位置是固定的，并从左到右，从1 到 V编号，编号为V 的花瓶在最右边。花束可以移动，并且每束花用1到F的整数唯一标识。标识花束的整数决定了花束在花瓶中的排列的顺序，如果i<j，则花束i必须放在花束j左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中。秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。
   每一个花瓶的形状和颜色也不同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空花瓶的美学值为0。在上述例子中，花瓶与花束不同的搭配所具有的美学值，可以用如下的表格表示：
　花瓶 1 (杜鹃花) 2 (秋海棠) 3 (康乃馨)
1 7 5 -21
2 23 21 5
3 -5 -4 -4
4 -24 10 -20
5 16 23 20


    根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放你在花瓶4中则显得很难看。为了取得最佳美学效果，必须保持花束顺序的条件下，使花的摆放取得最大美学值，如果具有最大美学值的摆放不止一种，则输出任意一种。

【输入格式】
第一行包含两个数： F, V。（1<=F<=100， F<=V<=100 ）
接下来的F行：包含V个数，输入Aij矩阵。 (-50<=Aij<=50，Aij为第i束花放在第j个花瓶中的美学值)

【输出格式】
第一行输出最大美学值
第二行给出方案

【输入样例】
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
【输出样例】
53
2 4 5

【参考程序】

1. //:============================“插花问题”的动态规划法算法============================
   
2. #define F 100
   
3. #define V 100
   
4. /**//*
   
5.     插花问题描述:
   
6.             将f束鲜花插入v个花瓶中,使达到最徍的视觉效果,
   
7.         问题相关约定及插花要求:
   
8.             鲜花被编号为1--f,花瓶被编号为1--v,花瓶按从小到
   
9.         大顺序排列,一只花瓶只能插一支花,鲜花i插入花瓶j中的
   
10.         视觉效果效果值已知,编号小的鲜花所放入的花瓶编号也小   
    
11.     问题求解思路:
    
12.             花瓶j(1<=j<=v)中插入鲜花的可能编号为[1..j](编号
    
13.         小的鲜花所放入的花瓶编号也小);
    
14.             设数组p[i][j]表示鲜花i插入花瓶j的好看程度,数组
    
15.         q[i][j]表示[1..i]束鲜花插入[1..j]个花瓶所能得到的最大
    
16.         好看程度,初始化q[0][0] = 0;q[0][j]=0(1<=j<=v),则q[f][v]
    
17.         是问题的解.
    
18.             特别地,j束鲜花插入到前面的j只花瓶中,所得到的好看
    
19.         程度是q[j][j] = p[1][1]+p[2][2]+...+[j][j].现将插花过
    
20.         程按花瓶排列顺序划分成不同阶段,则在第j阶段,第i束鲜花
    
21.         若放入第j号花瓶,最大好看程度是q[i-1][j-1]+p[i][j];第i束鲜
    
22.         花若放入前j-1个花瓶中的某一个,所得的好看程度是q[i][j-1],
    
23.         那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:
    
24.         q[i][j] = MAX(q[i-1][j-1]+p[i][j],q[i][j-1]),要使q[i][j]
    
25.         最大,应使q[i-1][j-1]和q[i][j-1]也最大
    
26. */
    
27. #define MAX(A,B) ((A) > (B) ? (A):(B))        //求取两数的最大值宏定义
    
28. #define F 100                    //鲜花数最大值常量定义
    
29. #define V 100                    //花瓶数最大值常量定义
    
30. //“插花问题”的初始化函数
    
31. //    int    f,v:        鲜花数量，花瓶个数
    
32. //    int    p[][v]:        鲜花i插入花瓶j的好看程度
    
33. void Flower_Initialize(int *f,int *v,int p[][V])
    
34. ...{
    
35.     int i,j;
    
36.     printf("输入鲜花数量及花瓶个数:");
    
37.     scanf("%d%d",f,v);
    
38.     printf("顺序输入各鲜花插入各花瓶的好看程度: ");
    
39.     for(i=1;i<=*f;i++)
    
40.         for(j=1;j<=*v;j++)
    
41.             p[i][j] = i*j;
    
42.             //scanf("%d",&p[i][j]);
    
43. }
    
44. //“插花问题”的动态规划法解决函数
    
45. //    int    p[][v]:        鲜花i插入花瓶j的好看程度
    
46. //    int    f,v:        鲜花数量，花瓶个数
    
47. //    int    *way:        鲜花插入花瓶的插入方法结果
    
48. int        Ikebana(int p[][V],int f,int v,int *way)
    
49. ...{
    
50.     int    i,j,q[F][V],newv;
    
51.     q[0][0] = 0;    //初始化[没有一束花插入花瓶时],好看程度自然为0
    
52.     //设置v个花瓶分别被插入v束鲜花时各号花瓶对应的(初始)最大好看程度
    
53.     for(j = 1;j <= v;j++)
    
54.     ...{
    
55.         q[0][j] = 0;
    
56.         //设置第j束鲜花放入第j号花瓶中的最大好看程度
    
57.         q[j][j] = q[j - 1][j - 1] + p[j][j];
    
58.     }
    
59.     for(j = 1;j <= v;j++)
    
60.         for(i = 1;i < j;i++)    //计算在第j阶段,插入第i束鲜花所能得到的最大好看程度
    
61.             q[i][j] = MAX(q[i - 1][j - 1] + p[i][j],q[i][j - 1]);
    
62.     newv = v;
    
63.     for(i = f;i > 0;i--)
    
64.     ...{
    
65.         while(q[i-1][newv-1]+p[i][newv] < q[i][newv])
    
66.             newv--;
    
67.         //确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶
    
68.         way[i] = newv--;
    
69.     }
    
70.     return(q[f][v]);
    
71. }
    
72. //测试“插花问题”的动态规划法函数
    
73. void    Run_Ikebana()
    
74. ...{
    
75.     //循环计数器，鲜花数量，花瓶个数，鲜花i插入花瓶j的好看程度，鲜花插入花瓶的插入方法结果
    
76.     int    i,f,v,p[F][V],way[F];
    
77.     Flower_Initialize(&f,&v,p);
    
78.     printf("最大好看程度点数为%d ",Ikebana(p,f,v,way));
    
79.     printf("插有鲜花的花瓶是: ");
    
80.     for(i = 1;i <= f;i++)
    
81.         printf("%4d",way[i]);
    
82. }
    
83. //:============================“插花问题”的动态规划法算法============================
    
84. int main(int argc, char* argv[])
    
85. ...{
    
86.     //Run_SubString();
    
87.     Run_Ikebana();
    
88.     printf(" 应用程序运行结束！ ");
    
89.     return 0;
    
90. }
    

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 14:36 编辑 ]

kon3155

【凸多边形三角划分】
    给定一个具有N(N<50)个顶点(从l到N编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小。
【输入格式】
第一行为顶点数N；
第二行为N个顶点(从1到N)的权值。
【输出格式】
最小的和的值。

【输入样例】
5
121 122 123 245 231
【输出样例】
12214884

【试题分析】
这是一道很典型的动态规划问题。设F[I,J]（I<J）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：
F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}     (I<K<J)
目标状态为：F[1,N]
但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形甚至实形的范围，所以我们还需用高精度计算，但这是大家的基本功，程序中就没有写了，请读者自行完成。
【三】参考程序

1. Var S                          :Array[1..50] Of Integer;
   
2.     F                          :Array[1..50,1..50] Of Comp;　
   
3.     D                     :Array[1..50,1..50] Of Byte;
   
4.     N                     :Integer;
   
5. Procedure Init;    (输入数据)
   
6. Var I                          :Integer;
   
7. Begin
   
8.   Readln(N);
   
9.   For I:=1 To N Do Read(S[I]);
   
10. End;
    
11. Procedure Dynamic;   （动态规划）
    
12. Var I,J,K                  :Integer;
    
13. Begin
    
14.   For I:=1 To N Do
    
15.     For J:=I+1 To N Do F[I,J]:=Maxlongint; （赋初始值）
    
16.   For I:=N-2 Downto 1 Do
    
17.     For J:=I+2 To N Do
    
18.       For K:=I+1 To J-1 Do       
    
19.         If (F[I,J]>F[I,K]+F[K,J]+S[I]*S[J]*S[K]) Then
    
20.           Begin
    
21.             F[I,J]:=F[I,K]+F[K,J]+S[I]*S[J]*S[K];
    
22.             D[I,J]:=K;     （记录父节点）
    
23.           End;           
    
24. End;
    
25. Procedure Print(I,J:Integer);  （输出每个三角形）
    
26. Begin
    
27.   If J=I+1 Then Exit;
    
28.   Write(',',I,' ',J,' ',D[I,J]);
    
29.   Out(I,D[I,J]);
    
30.   Out(D[I,J],J);
    
31. End;
    
32. Procedure Out;  （输出信息）
    
33. Begin
    
34.   Assign(Output,'Output.Txt'); Rewrite(Output);
    
35.   Writeln('The minimum is :',F[1,N]:0:0);
    
36.   Writeln('The formation of ',N-2,' triangle:');
    
37.   Write(1,' ',N,' 'D[1,N]);
    
38.   Out(1,D[1,N]);
    
39.   Out(D[1,N],N);
    
40.   Close(Output);
    
41. End;
    
42. Begin  （主程序）
    
43.   Init;
    
44.   Dynamic;
    
45.   Out;
    
46. End.
    

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 14:51 编辑 ]

kon3155

【快餐店】
    Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡、B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡、薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。
【输入格式】
输入文件共四行。第一行为三个不超过100的正整数A B C，分别表示该套餐汉堡、薯条和饮料的数量，中间以一个空格分开。第二行为3个不超过100的正整数P1,P2,P3分别为汉堡、薯条和饮料的单位生产耗时，中间以一个空格分开。第三行为生产线条数N(0≤N≤10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。
【输出格式】
输出文件仅一行，即每天套餐的最大产量。

【输入样例】
2 2 2
1 2 2
2
6 6
【输出样例】
1


【二】分析
本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。
状态表示： 用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,0<=k1<=k,且（j-j1）*p1+(k-k1)*p2<= 第I条生产线的生产时间)
但这样的算法是非常粗糙的，稍加分析可以发现，此算法的时间复杂度为O(N*1004),当N=10的时候，时间复杂度将达到10*1004=109，这是根本无法承受的。
于是，我们必须对算法进行进一步的优化，经仔细观察可以发现：这道题中存在着一个上限值（Min{100 div A, 100 div B, 100 div C}）,这是一个很好的判断条件，他可以帮我们尽早地求出最优解。为什么这样说呢？因为，在动态规划开始前，我们可以先用贪心法算出N条生产线可以生产的套数，如果大于上限值则可以直接输出上限值并退出。否则再调用动态规划，而在动态规划求解的过程中，也可以在每完成一阶段工作便和上限值进行比较，若大于等于上限值就退出，这样一来，就可以尽早的求出解并结束程序。
具体的算法流程为：


【三】小结
动态规划虽然是种高效的算法，但不加优化的话，有可能在时间和空间上仍然有问题，因此，在做题时要充分发掘题目中的隐含条件，并充分利用已知条件，这样才能令程序更快，更优。

【四】对程序优化的进一步讨论:
   本题在具体实现中还有一些优化的余地，在此提出，以供参考：
（1）        存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。
（2）        减少循环：在计算每一阶段状态过程中无疑要用到4重循环，其实这当中有很多是可以省掉的，我们可以这样修改每一重循环的起始值：
原起始值：                       改进后的起始值：
for I := 1 to n do begin               for I := 1 to n do begin
  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
{ 注：具体变量用途请参考程序　}
【五】参考程序

1. {\$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
   
2. {\$M 65520,0,655360}
   
3. 
   
4. program FastFood;
   
5. const
   
6.    input      = 'input2.txt';
   
7. 　output     = 'output2.txt';
   
8. var
   
9.    f        : text;
   
10.    r,p,pp    : array[0..100,0..100] of integer;　　｛pp:滚动数组中存放前一阶段的数组｝
    
11.    t,tot,tt    : array[0..10] of longint;  {tt:辅助数组；t:每条生产线的生产线时间；
    
12. tot:1-I条生产线生产时间的总和}
    
13.    n,a,b,c,p1,p2,p3   : longint;   {a,b,c:汉堡，薯条，饮料的个数；
    
14. p1,p2,p3汉堡，薯条，饮料的生产单位耗时}
    
15. 
    
16. procedure init;
    
17.   var
    
18.     i                           : integer;
    
19.   begin
    
20.     assign(f,input);
    
21.     reset (f);
    
22.     readln(f,a,b,c);
    
23.     readlN(f,p1,p2,p3);
    
24.     readln(f,n);
    
25.     for i := 1 to n do read(f,t[i]);
    
26.     close (f);
    
27.     if n=0 then begin  { 特殊情况处理 }
    
28.        assign(f,output);
    
29.        rewrite(f);
    
30.        writeln(f,0);
    
31.        close (f);
    
32.        halt;
    
33.     end;
    
34.   end;
    
35. 
    
36. function  min(i,j : longint) : longint;   {求两数中较小的一个}
    
37.   begin
    
38.        if i>j then min := j else min := i;
    
39.   end;
    
40. 
    
41. function  max(i,j : longint) : longint;   {求两数中较大的一个}
    
42. 
    
43.   begin
    
44.        if i>j then max := i else max := j;
    
45.   end;
    
46. 
    
47. procedure main;
    
48.   var
    
49.     q,q1,q2,i,j,k,j1,k1                 : longint;  {q:上限值；q1,q2 : A,B的上限值}
    
50.   begin
    
51.     q := min( 100 div a,min( 100 div b, 100 div c ) ); {求上限值}
    
52.     q1 := q*a;
    
53.     q2 := q*b;
    
54.     tt := t;
    
55.     i := 1;
    
56.     j := q1*p1;
    
57.     while (j>0) and (i<=n) do   { 用贪心法求出N条生产线可以生产的套数（可行解）}
    
58.           if j>tt[i] then begin
    
59.              dec(j,tt[i]);  tt[i] := 0; inc(i);
    
60.           end
    
61.           else begin dec(tt[i],j); j := 0; end;
    
62.     if j=0 then begin
    
63.        j := q2*p2;
    
64.        while (j>0) and (i<=n) do
    
65.              if j>tt[i] then begin
    
66.                 dec(j,tt[i]) ;tt[i] := 0; inc(i);
    
67.              end
    
68.              else begin dec(tt[i],j); j := 0; end;
    
69.        if j=0 then begin  {如果可行，直接输出上限值}
    
70.           assign(f,output);
    
71.           rewrite(f);
    
72.           writeln(f,q);
    
73.           close (f);
    
74.           halt;
    
75.        end;
    
76.     end;
    
77.     tot[0] := 0;
    
78.     for i := 1 to n do tot[i] := tot[i-1] + t[i];
    
79.     if tot[n] div (a*p1+b*p2+c*p3)<q then begin  {否则修改上限值}
    
80.        q := tot[n] div (a*p1+b*p2+c*p3);
    
81.        q1 := q*a;
    
82.        q2 := q*b;
    
83.     end;
    
84.     for i := 1 to n do begin
    
85.         for j := 0 to min(q1,t[i] div p1) do
    
86.             for k := 0 to min(q2,(t[i]-p1*j) div p2) do
    
87.                 r[j,k] := (t[i]-p1*j-p2*k) div p3;
    
88.         fillchar(p,sizeof(p),0);                  {数组清零}
    
89.         for j := 0 to min(q1,tot[i] div p1) do  
    
90.             for k := 0 to min(q2,(tot[i]-p1*j) div p2) do
    
91.              for j1 := max(0,j-t[i] div p1) to min(j,tot[i-1] div p1) do
    
92.               for k1 := max(0,k-(t[i]-(j-j1)*p1) div p2) to min(k,(tot[i-1]-p1*j1) div p2) do
    
93.                  if p[j,k] < pp[j1,k1] + r[j-j1,k-k1] then
    
94.                      p[j,k] := pp[j1,k1] + r[j-j1,k-k1];
    
95.         if p[q*a,q*b]>=q*c then begin
    
96.    {如果在此阶段产生了不小于上限值的解，则之际输出上限值，并直接退出}
    
97.            assign(f,output);
    
98.            rewrite(f);
    
99.            writeln(f,q);
    
100.            close (f);
     
101.            halt;
     
102.         end;
     
103.         pp := p;
     
104.         for j := 0 to min(100,tot[i] div p1) do
     
105.             for k := 0 to min(100,(tot[i]-p1*j) div p2) do
     
106.                 if p[j,k] > 100 then p[j,k] := 100;
     
107.     end;
     
108.     { out }
     
109.     k1 := 0;               { 输出最优值  }
     
110.     for j := 0 to 100 do
     
111.         if (j div a > k1) then
     
112.            for k := 0 to 100 do
     
113.                if (k div b > k1) and (p[j,k] div c > k1 ) then
     
114.                   k1 := min( min( j div a, k div b), p[j,k] div c );
     
115.     assign(f,output);
     
116.     rewrite(f);
     
117.     writeln(f,k1);
     
118.     close (f);
     
119.   end;
     
120. 
     
121. begin
     
122.    init;
     
123.    main;
     
124. end.
     

复制代码

g99

辛苦了