acm动态规划方案总结

Pkuacm1163theTriangle动态规划题目总结(一)

题目：

对于一种有数字构成二叉树，求由叶子到根一条途径，使数字和最大，如：

7

38

810

2744

45265

这个是典型动态规划，也是最最基本、最最简朴动态规划，典型多段图。思路就是建

立一种数组，由下向上动态规划，保存页了节点到当前节点最大值，Java核心代码如下：

for(inti=num-2;i>=0;i-){

for(intj=O;j<=i;」++){

//该句是整个动态规划核心

number[i][j]=Math./waj(number[i+1][j],number[i+1][j+1])-number[i][j];

)

}

带有•详细注释代码可以在获得

Pkuacm1579FunctionRunFun动态规划题目总结(二)

Considerathree-parameterrecursivefunctionw(a,b,c)：

ifa<=0orb<=0orc<=0,thenw(a,b,c)returns：1

ifa>20orb>20orc>20,thenw(a,b»c)returns：w(20,20,20)

ifa<bandb<c,thenw(a»b,c)returns：w(a»b»c-1)+w(a,b-1,c-1)-w(a,

b-l»c)

otherwiseitreturns：w(a-l»b,c)+w(a-Lb-1,c)+w(a-l»b,c-1)-w(a-1,b-1,

c-1)

这自身就是一种递归函数，要是按照函数自身写递归式，成果必定是TLE,这里我开了

一种三维数组,从w(0,0,0)开始递推,逐渐产生到w(20,20,20)值，复杂度0(\3).

总结：这道题是很地道DP,由于它了•问题实在是太多了，因此将问题成果保存起来，

刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上递推，这个例子就非常典型。总体

来说这个题目还是非常简朴，但是这个思想是地道动态规划。

带有详细注释代码可以在获得

Pkuacm2081Recaman'sSequence动态规划题目总结(三)

一道很简朴动态规划，依照一种递推公式求一种序列，我选取顺序求解，即自底向上递

推，一种int数组result依照前面值依此求出序列每一种成果，此外一种boolean数组

记录i与否已经出当前序列中，求result时候用得着，这样就避免了查找。核心

java代码为：

for(i=l;i<=500000：i++)

{

if(result[i-l]-i>O&&flag[result[i-l]-i]—false)

{

result[i]=result[i-l|-i;

flag[result[i-l]-i]=true：

)

else

resultti]=result[i-l]+i;

flagEresult[i-l]+i]=true：

)

}

带有详细注释代码可以在获得

Pkuacm1953WorldCupNoise动态规划题目总结(四)

给定一种不大于45整数n,求n位2进制数中不含相邻1数个数。看似简朴一道题,

如果当n=45时，对245次方检查，是无法完毕任务。先分析一下这个问题：

N以1结尾个数以()结尾个数总和

1112

2123

3••••・・•••

对于n=l来说，以1结尾、以0结尾个数都是1,总和是2,下面过度到2：对于所有

以1结尾数，背面都可以加上0,变为n=2时以0结尾，而只有结尾为0数才干加上1(由

于不能有两个持续0),这样就可以在n=2格里分别填上1、2,总和算出来为3,以此类推,

咱们可以算出所有水=45值，然后依照输入进行相应输出。核心代码如下：

inti,num,count,array[50][2],j=0:

array[l][1]=1;

array[1][0]=1;

for(i=2;i<50;i++)

{

array[i][0]=array[i-l][1];

arrayti][1]=array[i-l][l]+array[i-l][0];

)

咱们可以继续找出规律，其实这个就是斐波那切数列数列:

F[N]=F[N-l]+F[N-2];可以继续简化代码。

带有详细注释代码可以在获得

Pkuacm1458CommonSubsequence动态规划题目总结(五)

求两个siring最大公共字串.动态规划曲型问题.算法导论有详细解说.

下面以题目中例子来阐明算法：两个string分别为：abcfbc4Uabfca0创立一种二维数组

result□口，维数分别是两个字符串长度加一。咱们定义result1][j]表达X,和X最长子

串(LCS).当i或j等于。时，resu】t[i][j]=0.LCS问题存在一下递归式:

result[i][j]=0i=0orj=0

result[i][j]=result[i-l][j-l]+lX；==Y.i

result[i][j]=MAX(result[i-l][j]»rcsultti][j-1])XJ=Yj

对于以上例子，算法如下：

Result[i][j]:

abcfba

0123456

00000000

a101K1«I*1«1K

b20ii2X2*w9«2X24

f30142♦2A3K343«

c4014243文3A3A3A

a501K243A343A4K

从最后一种格向上顺着箭头方向可以找到最长子串构成，在有箭头构成线段中，具有斜

向上箭头相应字符是其中一种ICSo

Java代码核心某些如下：

for(inti=0;Klengthl;i++){

result[i][0]=0;

)

for(inti=0;i<length2;i++){

result[O][i]=0;

)

for(inti=l：i<=lengthl;i++){

for(intj=l;j<=length2;j++){

if(strl.charAt(i-l)==str2.charAt(j-D)

rpsnlt[i][j]=rpsnl[j-l]+1；

else

resultti][j]==

result[i-1][j]>result[i][j-l]?result[i-1][j]:result[i]J-l];

}

)

System.out.println(rcsult[lcngthl][length2]);

带有详细注释代码可以在获得

Pkuacm2250Compromise动态规划题目总结(六)

这个也是求最长公共字串，只是相比CommonSubsequence需要记录最长公共字串构成,

此时箭头标记就用上了，在程序中，用。pt□□存储标记，0表达朝向左上方，1表达指向上,

-1表达指向左。result□□存储当前最大字串长度。在求最优解时,顺着箭头从后向前寻

找公共字串序号，记录下来，输出即可。该算法在算法导论中有详细解说。

带有详细注释代码可以在获得。

Pkuacm1159Palindrome动态规划题目总结(七)

给一种字符串，求这个字符串至少增长几种字符能变成回文，如Ab3bd可以增长2个字

符变为回文：Adb3bdA。通过这样结论可以和最长公共子卡联系起来（未证明）：S和S'（注:S'

是S反串）最长公共子串其实一定是回文。这样咱们就可以借助les来解决该题，即用s长

度减去les值即可。核心Java代码为：

total-LCS（string,newStringBuffer（string）.reverseO.toStringO）;

〃函数ICS返问两个siringlr.s长度

带有详细注释代码可以在获得

Pkuacm1080HummanGeneFunction动态规划题目总结（八）

这是一道比较典型DP,两串基因序列包括A、C、G、T,每两个字母间匹配都会产生

一种相似值，求基因序列（字符串）匹配最大值v

这题有点像求最长公共子序列。只但是把求最大长度改成了求最大匹配值。用二维数组

。3口3］记录字符串a中前i个字符与字符串b中前j个字符匹配所产生最大值。如果已知

AG和GT最大匹配值，AGT和GT最大匹配值，AG和GTT最大匹配值，求AGT和GTT

最大匹配值，这个值是AG和GT最大匹配值加上T和T匹配值，AGT和GT最大匹配值

加上T和•匹配值，AG和GTT最大匹配值加上•和T匹配值中最大值，因此状态转移方程：

optlilUJ=

max(opt[i-J+table(b[i-l],a|j-l]),opt[i]Ij-l]+tableC-\a[j-l]),opt[i-l皿+table('-',b[i-1]));

NullAGTGATG

Null-3-5-6-8-11-12-14

G-2

T-3

T-4

A-7

G-9

第（）行，第0列表达null和字符串匹配状况，成果是'-'和各个字符累加:

for(i=l;i<=numl;i++)

opt[0][i]=opt[0][i-lJ+tableC*,a[i-l]);

for(i=l;i<=num2;i++)

opt[i][0]=opt[i-1][0]+table(，->,b[i-l]);

opt[num2][num]]即为所求成果。

带有详细注称代码可以在获得

Pkuacm2192Zipper动态规划题目总结(九)

这个题目规定判断2个字符串能否构成1个字符串,例如cat和tree能构成tcractOo

咱们定义一种布尔类型二维数组ai*ray,array[i][j]表达和str2[j]能否构成

str[i+j].i=0或者j=0表达空字符串,因此初始化时,array表达str1前j个字符

与否和str都匹配。

对于str=tcraete:

Nullcat

Null1000

t1

r0

e0

e0

可以证明:当array[i-l][j](array[i][j]上面一格)和array[i][j-1](array[i][j]

左而一格)都为0时，array[i][j]为。当array[i-l][j](array[i][j]上面一格)为1且左

面字母为str[i+j]时或者当arrayti][j-1](array[i][j]左面一格)为1且上面字母为

str[i+j]时，arrayti][j]为I.这就是状态转移方程为。

核心Java代码：

if(array[i][j-l]&&strl.charAt(j-l)==str.charAt(i+j-1)||array[i-1][j]&&str2.

charAt(i-l)==str.charA:(i+j-1))

arrayti][j]=true：

else

arrayti][j]=false;

带有详细注释代码可以在获得

Pkuacm3356AGTC动态规划题目总结(十)

一种字符串可以插入、删除、变化到另一种字符串，求变亿最小环节。和最长公共子序

列类似，用二维数组opt[i][二]记录字符串a中前i个字符到字符串b中前j个字符匹配所

需要最小步数。如果己知AG到GT最小步数，AGT到GT最小步数，AG到GTT最小步数，求

AGT到GTT最小步数，此时T==T,这个值是AG到GT最小步数，AGT到GT最小步数加一(AGT

到GT最小步数等于AGTT到GTT最小步数，加一是将T删除一步)，AG到GTT最小步数加一

(AG到GTT最小步数等于AGT到GTTT最小步数，加一是在AGT上增长T一步)。如果已知AG

到GT最小步数，AGA到GT最小步数，AG到GTT最小步数,求AGA到GTT最小步数,此时A!

=T,这个值是AG到GT最小步数加一(A变化为T),AGA到GT最小步数加一(AGA到GT最小

步数等于AGAT到GTT最小步数，加一是将T删除一步),AG到GTT最小步数加一(AG到GTT

最小步数等于AGA到GTTA最小步数，加一是在GTTA上删除A一步)。因此状态转移方程：

if(strl.charAt(i-l)==str2.charAt(j-1))

array[i][j]=Math,min(Math,min(array[i-l][j-1],array[i-1]+,

array[i][j-l]+l)；

else

array[i][j]=Math,min(Math.min(array[i-1],array[i-1][j]+l),

array[i][j-l]+D;

初始化时候和最长公共子序列不同，由于第0行，第0列表达null转化到字符串状况,

成果是字符串长度：

for(inti=0;i<=m;i++){

array[i][0]=i;

}

for(inti=0：i<=n;i++){

array[0][i]=i;

}

NullAGTGATG

Null01234567

G1

T2

T3

A1

G5

成果是array[m][n]

带有详细注释代码可以在获得

Pkuacm1887TestingtheCATCHER动态规划题目总结H)

题目论述很繁琐，其实就是求最长下降子序列，这一类题也是动态规划典型题。此类问

题有两种算法,一种T(o)=0(rf2),另一种T(o)=O(nlogn),这里用第一种,在1631

Bridgingsignals解题报告中简介第二种。

创立一种一维数组num_array[j],max_array[],num_array[j]表达序列元素，

max_array[i]表达以第i个元素结尾序列中最长下降子序列，初始化为1,对于一种

mtix_array[i],遍历前血每个兀素j,如果numarray[j]>numarray[i]且max_array[j]>=

max_array[i],那么max_airay[j]就要加1,因此递推公式为：

if(num_array[i]<=num_array[j]&&max_array[i]<=max_arrayJ])

max_array[i]++;

最后选最大一种max_array[i]就是最长下降子序列个数。Java核心某些代码：

for(inti=l;Klength;i++){

for(intj=O;j<i;j++){

if(num_array[i]<=num_array[j]&&max_array[i]<=max_array[j])

max_array[i]++：

}

max_value=(max_array[i]>max_value)?max_array[i]:max_value;

}

max_value是最后成果。

带有详细注释代码可以在获得

Pkuacm2533LongestOrderedSubsequence动态规划题目总结(十二)

这个题目和1887TestingtheCATCHER一模同样，没有什么值得说，核心c代码如下:

for(i=l;i<=n;i++)

(

for(j=l;j<i;j++)

if(max[i]<=max[j]&&num[i]>num[j])

max[i]++;

if(max[i]>result)

result=max[i];

}

printf(*%d\n*»result);

带有详细注择代码可以在获得

Pkuacm1631Bridgingsignals动态规划题目总结(十三)

这个题目可以转化为最长上升子序列，这样这个题目似乎就和2533LongestOrdered

Subsequence1887TestingtheCATCHER同样了,迅速写下代码,成果超时!看来只能用

O(nlogn)算法了。

在0(n"2)算法中:创立一种一维数组array[j],opt口，array[j]表达序列元素，opt[i]

表达以第i个元素结尾序列中最长下降子序列，初始化为1,对于一种。遍历前面每

个元素j,如果array[j]〉airay[i]且opt[j]>=opt[i],那么opt[j]就要加1,在这里,遍

历前面每个元素j,寻找此前最大子序列时间复杂度为0(n),如果咱们在一种有序序列中查

找此前最大序列长度，咱们就可以用一分查找，时间旬杂度就会降为O(kgn),总时间品杂

度就会为O(nlogn)。为此，咱们增长一种一维数组B,B[i]表达当前序列为i末尾元素最小

值。例如对于序列：426315：

123456

array426315

opt112213

B135

构建过程如下：

i=l时,opt[i]=lB[i]=4(当前为1序列末尾元素最小值)

opt111111

B4

i=2时,2不不不大于4,因此opt[i]=l,将B[l]更新为2

opt111111

B2

i=3时,6不不大于2,因此opt[i]=l+l,将B[2]更新为6

opt112111

B26

i=4时,3在26之间，因此opt[i]=l+l,将B[2]更新为3

opt112211

B23

i=5时，1不大于2,因此opt[i]=l,将B[l]更新为1

opt112211

B13

i=6时，5不不大于3,因此opt[i]=2+l,将B[3]更新为5

opt112213

B135

opl[6]就是最后成果。从构建过程可以容易证明一下两点：B是递增。B是当前序列为

i末尾元素最小值。以上“2天不不大于4”，“3在26之间”等等判断采用二分查找，因此

总时间复杂度为：O(nlogn),核心c代码如下:

for(i=l;i<=n;i++)

{

num=array[i];

Ipft=1：

right=Blcn;

while(left<=righ:)

(

mid=(left+right)/2;

if(B[mid]<num)

left=mid+1;

else

right=mid-1;

)

opt[i]=left;

B[left]=num:

if(Blen<left)

Bien=left;

if(max<opt[i])

max=op:[i];

}

printf(飞d\n",max);

带有详细注释代码可以在获得

Pkuacm1157LITTLESHOPOFFLOWERS动态规划题目总结(十四)

该题也是典型动态规划，题目论述依然很麻烦，其实简化一下就是这样：例如下面这个

例子就是：3表达行，5表达列，然后在下面3行5列每一行选一种数，使这3个数最大，

规定选数列数必要依次增大，就是从左上方向右下方选3个数变和最大。

35

723-5-2416

521-41023

-215-4-2020

咱们用。Pt定义以当前Ij为结尾花排序最大值，用r*(-50)表达负无穷，初始化时第

一行为origin背面为r*(-50)

Opt[][]12345

1723-5-2416

2-150-150-150-150-150

3-150-150-150-150-150

从第二行开始，对于第i行第j歹iJ,对于i>=j,遍历i・l行前j歹求出当前最大值。

Opt[]□12345

1723-5-2416

2-15021+7-4+max(7,23,-5)10+max(7,23,-5,-24)23+max(…)

3-150-150-150-150-150

1=3:

12345

1723-5-2416

2/p>

3-150-150-4+max(-150,28)-20+max()20+max(-150,28,19,33)

最后取第i行最大值即可，核心c代码:

for(i=2;i<=r;i++)

for(j=l;j<=c;j++)

if(j>=i)

for(k=l;k<j;k++)

if(opt[i][j]<opt[i-l][k]+origin[i][j])

opt[i][j]=opt[i-l]-k]+origin[i][j];

带有详细注释代码可以在获得

Pkuacm1088滑雪动态规划题目总结(十五)

12345

161718196

152425207

142322218

131211109

一种人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上而例子中，

一条可滑行滑坡为24T7-16-1。固然25-24-23-...-3-2T更长.事实上,这是最长一条。

输出最长区域长度。

表达位置ij上最大下降距离，如果其周边4个点存在高度比ij高，且。pt

没有ij大点，则。[周边]+1：此外，这个问题中存在大量重复问题，应当将

计算成果存储起来，避免重复计算。

核心某些c代码为：

for(k=0;k<4;k++)

(

if(isln(i+dx[k],j+dy[k])&&heigth[i][J]<heigth[i+dx[k]][j+dy[k]])

(

intnum=dp(i+dx[k],j+dy[k]);

if(opt[i][j]<=num)

opt[i][j]=num+1;

)

)

}

其中constintdx[]={0,0,-1,l},(iy[]=[-1,1,0,0};表达一种点周边4个点.带

有详细注释代码可以在获得

Pkuacm1050TotheMax动态规划题目总结(十六)

题目意思很简朴，在一种矩阵里面找它子矩阵，使得子矩阵数值之和到达最大。其实就

是最大子段和问题在二维空间上推广。先说一下一维状况吧：设有数组a0,al…an,找出其

中持续子段，使它们和达到最大。如果对于子段：92-162表达以ai结尾子段

中最大子段和。在已知temp[i]状况下，求temp[i+1]办法是；

如果temp[i]>0temp[i+l]=temp[i]+ai(维续在前一种子段上加上ai),否则

temp[i+l]=ai(不加上前面子段)，也就是说状态转移方程：

temp[i]=(temp[il]>0?teir.p[i1]:0)ibuf[i];

对于刚才例子icmp：911-52,然后取icmp口中最大就是一维序列最大子段。求一维最

大子段和函数：

intgetMax(intbuf[100],intn)

(

inttemp[101],max=n*(-127);

memset(temp,0,4*(n+D);

for(inti=l;i<=n;i++)

temp[i]=(temp[i-l]>O?temp[i-l]:0)+buf[i];

if(max<temp[ij)

max=temp[i];

)

rplurnmax;

}

下面扩展到二维状况：考察下面题目中例子：

0-2-70

92-62

-41-47

-180-2

咱们分别用ij表达起始行和终结行，遍历所有也许：

for(i=l;i<=n;i++)

for(j=i;j<=n;j++){}

咱们考察其中一种状况i=2j=4,这样就相称与选中了234三行，求那儿列组合能获得最

大值，由于总昂234行，因此咱们可以将这3行“捆绑”起来，变为求

4(9-4-1),11(8+2+1),-1066-4+0),7(7+2-2)最大子段和，ok,问题成功转化为一维状况！

带有详细注释代码可以在获得

Pkuacm1014Dividing动态规划题目总结(十七)

刚AC了，趁热打铁，写《解题报告，这道题很早就在joj上做过，当时不懂得dp,只

会用很菜办法，成果虽然joj这道题仅规定10s还是会超时！

思想：本题是找按价值均分大理石方案与否存在，由于分派时不能破坏大理石，因此有

个显而易见剪枝：当所有大理石总价值为奇数时必定不能被均分。把问题转化一下即：由一

种人能否从原大理石堆中取出总价值为本来一半大理石，本题重要和法是动态规划，数组

flag代表状态，设总价值为sum.当flag[k]=true时，阐明,可以有一人获得价值k,此外

一人获得价值V-k大理石分派方案。反之若flag[k]=false阐明这种分派方案不存在.咱们

任务就是计算出flag[sum/2]是true还是false,显然有flag'O]==true方案存在,即一种

人什么都不分，此外一种人拿走所有大理石.

设i(1«6)为石头价值，试想若flag[k]=true,如果能再向k中增长一价值为i大理石,

则flag[k+i]==true必然成立.石头有两个属性，一种是价值另一种是数量，这里array[i]

代表价值为i大理石数量，咱们依照其中一种属性；价值来划分阶段。即

for(inti=l;i〈=6;i++),flag[k]表达状态与否存在(这里状态是指能否从原石头堆中

分出价值为k新石头堆)。在初始阶段是i=l,初始状态是flag[O]=true,max代表当前满足

flag[k]==truc这一条件k最大值。

for(intj=max;j>=0;j­)

〃从当前最大值flag开始，依照前面提到flag[j]==true成立则flag[j+i]==true亦成立

理论，在原有状态flag[j]==true已存在条件下加入stone[i]阶段石头,得到新状态

还是举个例子吧：301200

flag门:sum/2=6

i0123456

flag[]:1000()00

对于i=larray[l]=3由于flag[0]=true,因此,flag[2],flag[3]都变为true：

i0123456

flag[]:1111000

对于i=2array[2]=0不考察

对于i=3array[3]=1由于flag[0]flag[l],flag[2],flag[3]=true,因此flag[3],

flag⑷,flag[5],flag[6]都变为true：

i()12345n

flag[]:1111111

等等等等，咱们任务是判断flag[sum/2]与否为真。

这样程序基本框架就有了：dr：函数如下：

booldp(intarray[7])

{

boolflag[60001];

inti,j,k,sum=0,max=0;

for(i=1;i<=6;i++)

sum+=array[i]*i;

if(sum%2!=0)

returnfalse;

memset(flag,0,sizeof(flag));

flag[0]=true;

for(i=l;i<=6：i++)

(

if(array[i]>0)

(

for(j=max;j>=C;j-)〃至于为什么要从大到小，写成从小到大，调试一下

就可以看出问颗，//例如有1个1,本来fladO]=true,循环一遍后=true,此

时再判断flag[l]=true,继续flag[2]=true就不〃合题意了,从大到小可以解决这个问

题

(

|

for(k=1;k<=array[i];k++)

if(j+k*i==sum/2)

returntrue;

elseif(j+k*i<sum/2&&!flag[j+kxi])

(

if(j+k*i>max)max=j+k*i;

if(j+k*i>sum/2)max=sum/2;

门ag[j+k*i]=tnip;

)

}

)

}

}

)

returnfalse：

}

这样问题就解决了，submit,成果超时，从joj上试了一下，成果ac,6s多，距离pojls

还很远。咱们考察如果flag[j4-k*i]已经等于true,就不用继续循环下一种k了，直接break

就可以了，详细因素是这样：

假设当前flag口序列是这样：1101101101,当前考察是i=3：array[i]=5,

就是要在这个基本上加上5个3,按照程序意思、，从最后一种1开始依此加上3,将其值变

为I,一共加上5个，然后在倒数第二个1上依此加上3,将其值变为1,一共加上5个，

这个过程不会碰见flag=l状况，给倒数第三个1依此加3时候，会遇到：flag=l,这个时候

就可以break了，由于这时候还需要加4个3都在最后一种1加5个3时候加过了，这里要

注意是，给每个1加上3时候，只会遇到“旧”flag=l,不会遇到新增长flag=l,而旧1已

经加过了array[i]个i,因此就不用加了，直接退出就行了。

修改后裔码:

for(i=l;i<=6;i++)

if(array[i]>0)

(

for(j=max;j>=C;j­)

(

if(flag[j])

{

for(k=l;k<=array[i];k++)

(

if(j+k*i==sum/2)

returntrue;

if(j+k*i>sum/2|flag[j+k*i])

break;

flag[j+k*i]=true;

}

)

}

)

max+=array[i]*i;

if(max>sum/2)max=sum/2;

}

这样就ac了。Omso

带有详细注释代码可以在获得

Pkuacm1160postoffice动态规划题目总结(十八)

题目给出m个村庄及其距离，给出n个邮局，规定怎么建n个邮局使代价最小。

思路：用记录把前i个邮局建到前j个村庄中最优解，用记录

所有在i到j村正中，建1个邮局最小代价。显然邮局应当设到中点。让前i个邮局覆盖前

j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k〈=n),则状态转移方程为

opt[i+l][j+k]=min{opt[i][j]+cost[j+l][j+k];}(k+j<=n)

Cost数组存储从i到j中有一种邮局最小代价，显然该邮局应当放在中间，构造cost

代码和成果如下：

for(i=l;i<=m;i++)

for(j=i;j<=m;j++)

cost[i][j]=0;

mid=(i+」)/2;

for(k=i;k<=j;k++)

cost[i][j]+=(distance[mid]-distance[k])>=0?

distanceImid]-distanceIkl:distanceFkl-distanceFmidl:

CostEi][j]12345678910

101261016213774117

2014811163168109

30347112661102

40137205594

5024175089

602134674

70113361

802228

906

100

Opt[i][j]表达前i个邮局覆盖前j个村庄最小代价,对于i=l来说，opt[i][j]=

cost[i][j],让前2个邮局覆盖前j个村庄，也就是i=2状况，也许是一下状况最优解：第

一种邮局覆盖第一种村庄，第二个邮局覆盖2-j个村庄，或者第一种邮局覆盖第1-2个村庄,

第二个村庄覆盖3-j个村庄，第一种邮局覆盖第1-3个村庄，第二个村庄覆盖4-j个村庄，

等等等等。该某些代码如下：

far(i=O：i<=n：i++)

for(j=0;j<=m：j++)

if(opt[i][j]<3000000)

(

for(k=l;j+k<=m;k++)

(

if(opt[i+l][j+k]>opt[i][j]+cost[j+l][j+k])

(

opt[i+l][j+k]=opt[i][j]+cost[j+l][j+k]:

)

）

Opt[i][j]012345678910

00

101261016213774117

20148->511->816->1231->2768->62109->103

3

4

5

带有详细注释代码可以在获得

Pkuacm1125StockbrokerGrapevine动态规划题目总结（十九）

有向图中每一对顶点间最短途径问题，典型弗洛伊德克法。

问题描述：已知一种具有n个顶点各边权值均不不大于0带权有向图，对每对顶点vi!=vj,

规定求出每•对顶点之间最短途径和最短途径长度。

解决方案：弗洛伊德(floyd)算法

弗洛伊德算法中采用带权邻接矩阵cost表示狗•向网•当边Vv.,v,＞不存在时.

cost[i]m=max•当i=j时,cost[i][j]=0;即对角线上的元素为。,设置一个二维数组A

用于存放当前顶点之间的最短路往长度,分址表示当前顶点v,到顶点v,的用短

路柱长度.

弗洛伊德算法的基本思想是：递推产生一个矩阵序列儿，人|一・・,人卜，・・・，人“，其中

表示从顶点V,到顶点v,的路径上所经过的顶点序号不大于k的最短路径长度・

初始时，有A,Rm=cost[i：KA等于图的邻接矩阵cosu,儿[口卬表示从i到j不经过

任何中间顶点的最短路在K度.当求从顶点v,到顶点v,的路径上所经过的顶点序号不

大于k+1的最短路径K度时•要分两种情况考虑•一种情况是该路径不经过顶点序号为

k+1的顶点，此时该路径K度与从顶点v,到顶点v,的路径上所经过的顶点序号不大于k

的最短路径长度相同；另一种情况是从I#点V,到顶点V,的最短路径上经过序号为k+1

的顶点，那么•该路径可分为两段•一段是从顶点V,到顶点VkT的最短路径,另一段是从

顶点V-I到JI点V,的最短路泾•此时最短路径长度等于这两段路径长度之和.这两种情

况中的较小值,就是所要求的从顶点V,到II点V,的路径上所经过的顶点序号不大于k+】

的最短路径.

对于这样i种例子:

A0[i][j]=cost[i][j]:

A0123A1123

10451045

2206220min(6,2+5)

322032min(2,2+4)0

A2123A3123

104min(5,4+6)10min(4,5+2)5

22062min(2,6+2)06

3min(2,2+2)203220

核心c代码如下:

for(intk=l;k<=n;k++)〃生成AO,Al,A2...循环

for(inti=l：i<=n;i++)〃行

for(intj=l;j<=n：j++)//列

〃如果是i=k||j=k||i=j就保持不变,否则取最小值

array[i][j]=(i=k||j==k||i==j)?array[i][j]:

((arrayti][j]<(array[i][k]+array[k][j])?array[i][j]:(array[i][k]+array[k][j])))

V

最后依照题意，取每行最大值中最小值即可。

带有详细注释代码可以在获得

Pkuacm1179Polygon动态规划题目总结(二十)

多边形游戏是一种单人玩游戏，开始时有一种由n个顶点构成多边形。每个顶点被赋予

一种整数值，每条边被赋予一种运算符“+”或“*”。所有边依次用整数从1到n编号。

游戏第1步，将•条边删除。

随后n-1步按如下方式操作：

(1)选取一条边E以及由E连接着2个顶点VI和V2；

⑵用一种新顶点取代边E以及由E连接着2个顶点VI和V2»将由顶点VI和V2整数值通

过边E上运算得到成果赋了，新顶点。

最后，所有边都被删除，游戏结束。游戏得分就是所剩顶点上整数值。

问题:对于给定多边形，计算最高得分。分析：

•在所给多边形中,从顶点i(lWiWn)开始,长度为义链中有」个顶点)顺时针链p(i,

j)可表达为v[i],op[i+l],…，v[i+j-l]o

•如果这条链最后一次合并运算在。p[i+s]处发生(lWsWj-1),则可在op[i+s]处将

链分割为2个子链p(i,s)和p(i+s,j-s).

•设ml是对子锌p(i,s)任意一种合并方式得到值，而