acm动态规划方案总结.doc

Pku acm 1163 the Triangle 动态规划题目总结(一)
题目：
对于一种有数字构成二叉树，求由叶子到根一条途径，使数字和最大，如：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这个是典型动态规划，也是最最基本、最最简朴动态规划，典型多段图。思路就是建立一种数组，由下向上动态规划，保存页子节点到当前节点最大值，Java核心代码如下：
for(int i=num-2;i>=0;i--){
for(int j=0;j<=i;j++){
//该句是整个动态规划核心
number[i][j]=Math.max(number[i+1][j],number[i+1][j+1])+number[i][j];
}
}
带有详细注释代码可以在获得

Pku acm 1579 Function Run Fun 动态规划题目总结(二)

Consider a three-parameter recursive function w(a，b，c)：
if a <= 0 or b <= 0 or c <= 0，then w(a，b，c) returns：1
if a > 20 or b > 20 or c > 20，then w(a，b，c) returns：w(20，20，20)
if a < b and b < c，then w(a，b，c) returns：w(a，b，c-1) + w(a，b-1，c-1) - w(a，b-1，c)
otherwise it returns：w(a-1，b，c) + w(a-1，b-1，c) + w(a-1，b，c-1) - w(a-1，b-1，c-1)
这自身就是一种递归函数，要是按照函数自身写递归式，成果必定是TLE，这里我开了一种三维数组，从w(0,0,0)开始递推，逐渐产生到w(20,20,20)值，复杂度O(n^3).
总结：这道题是很地道DP，由于它子问题实在是太多了，因此将问题成果保存起来，刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上递推，这个例子就非常典型。总体来说这个题目还是非常简朴，但是这个思想是地道动态规划。
带有详细注释代码可以在获得

Pku acm 2081 Recaman's Sequence 动态规划题目总结(三)

一道很简朴动态规划，依照一种递推公式求一种序列，我选取顺序求解，即自底向上递推，一种int数组result依照前面值依此求出序列每一种成果，此外一种boolean数组flag[i]记录i与否已经出当前序列中，求result时候用得着，这样就避免了查找。核心java代码为：
for(i=1;i<=500000;i++)
{
if(result[i-1]-i>0&&flag[result[i-1]-i]==false)
{
result[i] = result[i-1]-i;
flag[result[i-1]-i] = true;
}
else
{
result[i] = result[i-1]+i;
flag[result[i-1]+i] = true;
}
}
带有详细注释代码可以在获得

Pku acm 1953 World Cup Noise 动态规划题目总结(四)

给定一种不大于45整数n，求n位2进制数中不含相邻1数个数。看似简朴一道题，如果当n=45时，对245次方检查，是无法完毕任务。先分析一下这个问题：
N
以1结尾个数
以0结尾个数
总和
1
1
1
2
2
1
2
3
3
…
…
…
对于n=1来说，以1结尾、以0结尾个数都是1，总和是2，下面过度到2：对于所有以1结尾数，背面都可以加上0，变为n=2时以0结尾，而只有结尾为0数才干加上1（由于不能有两个持续0），这样就可以在n=2格里分别填上1、2，总和算出来为3，以此类推，咱们可以算出所有n<=45值，然后依照输入进行相应输出。核心代码如下：
int i,num,count,array[50][2],j=0;
array[1][1] = 1;
array[1][0] = 1;
for(i=2;i<50;i++)
{
array[i][0] = array[i-1][1];
array[i][1] = array[i-1][1]+array[i-1][0];
}
咱们可以继续找出规律，其实这个就是斐波那切数列数列：
F[N] = F[N-1]+F[N-2];可以继续简化代码。
带有详细注释代码可以在获得
Pku acm 1458 Common Subsequence 动态规划题目总结(五)

求两个string最大公共字串，动态规划典型问题。算法导论有详细解说。
下面以题目中例子来阐明算法：两个string分别为：abcfbc和abfca。创立一种二维数组result[][],维数分别是两个字符串长度加一。咱们定义result[i][j]表达Xi和Yj 最长子串(LCS).当i或j等于0时，result[i][j]=0. LCS问题存在一下递归式：
result[i][j] = 0 i=0 or j=0
result[i][j] = result[i-1][j-1]+1 Xi= =Yj
result[i][j] = MAX(result[i-1][j]，result[i][j-1]) Xi！=Yj
对于以上例子，算法如下：
Result[i][j]:

a
b
c
f
b
a

0
1
2
3
4
5
6

0
0
0
0
0
0
0
0
a
1
0
1
1
1
1
1
1
b
2
0
1
2
2
2
2
2
f
3
0
1
2
2
3
3
3
c
4
0
1
2
3
3
3
3
a
5
0
1
2
3
3
3
4
从最后一种格向上顺着箭头方向可以找到最长子串构成，在有箭头构成线段中，具有斜向上箭头相应字符是其中一种lcs。
Java代码核心某些如下：
for(int i=0;i<length1;i++){
result[i][0] = 0;
}
for(int i=0;i<length2;i++){
result[0][i] = 0;
}
for(int i=1;i<=length1;i++){
for(int j=1;j<=length2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1))
result[i][j] = result[i-1][j-1]+1;
else
result[i][j]= = result[i-1][j]>result[i][j-1]?result[i-1][j]:result[i][j-1];
}
}
System.out.println(result[length1][length2]);

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

Pku acm 2250 Compromise 动态规划题目总结(六)

这个也是求最长公共字串，只是相比Common Subsequence需要记录最长公共字串构成，此时箭头标记就用上了,在程序中，用opt[][]存储标记，0表达朝向左上方，1表达指向上，-1表达指向左。result[][]存储当前最大字串长度。在求最优解时，顺着箭头从后向前寻找公共字串序号，记录下来，输出即可。该算法在算法导论中有详细解说。
带有详细注释代码可以在获得。

Pku acm 1159 Palindrome 动态规划题目总结(七)

给一种字符串，求这个字符串至少增长几种字符能变成回文，如Ab3bd可以增长2个字符变为回文：Adb3bdA。通过这样结论可以和最长公共子串联系起来(未证明)：S和S' (注:S'是S反串)最长公共子串其实一定是回文。这样咱们就可以借助lcs来解决该题，即用s长度减去lcs值即可。核心Java代码为：
total-LCS(string,new StringBuffer(string).reverse().toString());
//函数LCS返回两个stringlcs长度
带有详细注释代码可以在获得

Pku acm 1080 Humman Gene Function 动态规划题目总结(八)

这是一道比较典型DP，两串基因序列包括A、C、G、T，每两个字母间匹配都会产生一种相似值，求基因序列（字符串）匹配最大值。
这题有点像求最长公共子序列。只但是把求最大长度改成了求最大匹配值。用二维数组opt[i][j]记录字符串a中前i个字符与字符串b中前j个字符匹配所产生最大值。如果已知AG和GT最大匹配值，AGT和GT最大匹配值，AG和GTT最大匹配值，求AGT和GTT最大匹配值，这个值是AG和GT最大匹配值加上T 和T匹配值，AGT和GT最大匹配值加上T 和-匹配值，AG和GTT最大匹配值加上-和T匹配值中最大值，因此状态转移方程：
opt[i][j] = max(opt[i-1][j-1]+table(b[i-1],a[j-1]),opt[i][j-1]+table('-',a[j-1]),opt[i-1][j]+table('-',b[i-1]));

Null
A
G
T
G
A
T
G
Null

-3
-5
-6
-8
-11
-12
-14
G
-2

T
-3

T
-4

A
-7

G
-9

第0行，第0列表达null和字符串匹配状况，成果是’-’和各个字符累加： for(i=1;i<=num1;i++)
opt[0][i] = opt[0][i-1]+table('-',a[i-1]);
for(i=1;i<=num2;i++)
opt[i][0] = opt[i-1][0]+table('-',b[i-1]);
opt[num2][num1]即为所求成果。
带有详细注释代码可以在获得
Pku acm 2192 Zipper 动态规划题目总结(九)

这个题目规定判断2个字符串能否构成1个字符串，例如cat和tree能构成tcraete。咱们定义一种布尔类型二维数组 array,array[i][j]表达str1[i]和str2[j]能否构成str[i+j].i=0或者j=0表达空字符串，因此初始化时，array[0][j]表达str1前j个字符与否和str都匹配。
对于str=tcraete:

Null
c
a
t
Null
1
0
0
0
t
1

r
0

e
0

e
0

可以证明：当array[i-1][j]( array[i][j]上面一格)和array[i][j-1]( array[i][j]左面一格)都为0时，array[i][j]为0.当array[i-1][j]( array[i][j]上面一格)为1且左面字母为str[i+j]时或者当array[i][j-1]( array[i][j]左面一格)为1且上面字母为str[i+j]时，array[i][j]为1.这就是状态转移方程为。
核心Java代码：
if(array[i][j-1]&&str1.charAt(j-1)==str.charAt(i+j-1)||array[i-1][j]&&str2.charAt(i-1)==str.charAt(i+j-1))
array[i][j] = true;
else
array[i][j] = false;
带有详细注释代码可以在获得

Pku acm 3356 AGTC 动态规划题目总结(十)

一种字符串可以插入、删除、变化到另一种字符串，求变化最小环节。和最长公共子序列类似，用二维数组opt[i][j]记录字符串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(str1.charAt(i-1)==str2.charAt(j-1))
array[i][j] = Math.min(Math.min(array[i-1][j-1]，array[i-1][j]+1)，array[i][j-1]+1);
else
array[i][j] = Math.min(Math.min(array[i-1][j-1]+1，array[i-1][j]+1)，array[i][j-1]+1);
初始化时候和最长公共子序列不同，由于第0行，第0列表达null转化到字符串状况，成果是字符串长度：
for(int i=0;i<=m;i++){
array[i][0] = i;
}
for(int i=0;i<=n;i++){
array[0][i] = i;
}

Null
A
G
T
G
A
T
G
Null
0
1
2
3
4
5
6
7
G
1

T
2

T
3

A
4

G
5

成果是array[m][n]
带有详细注释代码可以在获得

Pku acm 1887 Testing the CATCHER 动态规划题目总结(十一)

题目论述很繁琐，其实就是求最长下降子序列，这一类题也是动态规划典型题。此类问题有两种算法，一种 T(o) = O(n^2),另一种T(o) = O(nlogn),这里用第一种，在1631 Bridging signals解题报告中简介第二种。
创立一种一维数组num_array[j]，max_array[],num_array[j]表达序列元素，max_array[i]表达以第i个元素结尾序列中最长下降子序列，初始化为1，对于一种max_array[i]，遍历前面每个元素j，如果num_array[j]> num_array[i]且max_array[j]>= max_array[i],那么max_array[j]就要加1，因此递推公式为：
if(num_array[i]<=num_array[j]&&max_array[i]<=max_array[j])
max_array[i]++;
最后选最大一种max_array[i]就是最长下降子序列个数。Java核心某些代码：
for(int i=1;i<length;i++){
for(int j=0;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是最后成果。
带有详细注释代码可以在获得

Pku acm 2533 Longest Ordered Subsequence 动态规划题目总结(十二)

这个题目和1887 Testing the CATCHER一模同样，没有什么值得说，核心c代码如下：
for(i=1;i<=n;i++)
{
for(j=1;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);
带有详细注释代码可以在获得

Pku acm 1631 Bridging signals 动态规划题目总结(十三)

这个题目可以转化为最长上升子序列，这样这个题目似乎就和2533 Longest Ordered Subsequence 1887 Testing the CATCHER同样了，迅速写下代码，成果超时！看来只能用O(nlogn)算法了。
在O(n^2)算法中：创立一种一维数组array[j]，opt[],array[j]表达序列元素，opt[i]表达以第i个元素结尾序列中最长下降子序列，初始化为1，对于一种opt[i]，遍历前面每个元素j，如果array[j]>array[i]且opt[j]>=opt[i],那么opt[j]就要加1，在这里，遍历前面每个元素j，寻找此前最大子序列时间复杂度为O(n)，如果咱们在一种有序序列中查找此前最大序列长度，咱们就可以用二分查找，时间复杂度就会降为O(logn),总时间复杂度就会为O(nlogn)。为此，咱们增长一种一维数组B，B[i]表达当前序列为i末尾元素最小值。 例如对于序列：4 2 6 3 1 5 ：
i
1
2
3
4
5
6
array
4
2
6
3
1
5
opt
1
1
2
2
1
3
B
1
3
5

构建过程如下：
i=1时，opt[i]=1 B[i]=4(当前为1序列末尾元素最小值)
opt
1
1
1
1
1
1
B
4

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

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

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

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

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

opt[6]就是最后成果。从构建过程可以容易证明一下两点：B是递增。B是当前序列为i末尾元素最小值。以上“2不不不大于4”，“3在2 6之间”等等判断采用二分查找，因此总时间复杂度为：O(nlogn)，核心c代码如下：
for(i=1;i<=n;i++)
{
num = array[i];
left = 1;
right = Blen;
while(left<=right)
{
mid = (left+right)/2;
if(B[mid]<num)
left = mid+1;
else
right = mid-1;
}
opt[i] = left;
B[left] = num;
if(Blen<left)
Blen = left;
if(max<opt[i])
max = opt[i];
}
printf("%d\n",max);

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

Pku acm 1157 LITTLE SHOP OF FLOWERS 动态规划题目总结(十四)

该题也是典型动态规划，题目论述依然很麻烦，其实简化一下就是这样：例如下面这个例子就是：3表达行，5表达列，然后在下面3行5列每一行选一种数，使这3个数最大，规定选数列数必要依次增大，就是从左上方向右下方选3个数使和最大。
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
咱们用opt定义以当前I j为结尾花排序最大值，用r*(-50)表达负无穷，初始化时第一行为origin[i][j]，背面为r*(-50)
Opt[][]
1
2
3
4
5
1
7
23
-5
-24
16
2
-150
-150
-150
-150
-150
3
-150
-150
-150
-150
-150
从第二行开始，对于第i行第j列，对于i>=j,遍历i-1行前j列,求出当前最大值。
Opt[][]
1
2
3
4
5
1
7
23
-5
-24
16
2
-150
21+7
-4+max(7,23,-5)
10+max(7,23,-5,-24)
23+max(…)
3
-150
-150
-150
-150
-150
I=3:
Opt[][]
1
2
3
4
5
1
7
23
-5
-24
16
2
-150
28
19
33
46
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=1;j<=c;j++)
if(j>=i)
for(k=1;k<j;k++)
if(opt[i][j]<opt[i-1][k]+origin[i][j])
opt[i][j]=opt[i-1][k]+origin[i][j];

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

Pku acm 1088 滑雪 动态规划题目总结(十五)

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一种人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面例子中，一条可滑行滑坡为24-17-16-1。固然25-24-23-...-3-2-1更长。事实上，这是最长一条。输出最长区域长度。
Opt[i][j]表达位置i j上最大下降距离，如果其周边4个点存在高度比i j高，且opt没有ij 大点，则opt[i][j]=opt[周边]+1；此外，这个问题中存在大量重复问题，应当将计算成果存储起来，避免重复计算。
核心某些c代码为：
for(k=0;k<4;k++)
{
if(isIn(i+dx[k],j+dy[k]) && heigth[i][j]<heigth[i+dx[k]][j+dy[k]])
{
int num = dp(i+dx[k],j+dy[k]);
if(opt[i][j]<=num)
{
opt[i][j] = num+1;
}
}
}
其中const int dx[] = {0,0,-1,1},dy[] = {-1,1,0,0};表达一种点周边4个点。带有详细注释代码可以在获得

Pku acm 1050 To the Max 动态规划题目总结(十六)

题目意思很简朴，在一种矩阵里面找它子矩阵，使得子矩阵数值之和到达最大。其实就是最大子段和问题在二维空间上推广。先说一下一维状况吧：设有数组a0,a1…an,找出其中持续子段，使它们和达到最大。如果对于子段：9 2 -16 2 temp[i]表达以ai结尾子段中最大子段和。在已知temp[i]状况下，求temp [i+1]办法是：
如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一种子段上加上ai),否则temp[i+1]=ai(不加上前面子段)，也就是说 状态转移方程：
temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
对于刚才例子 temp： 9 11 -5 2，然后取temp[]中最大就是一维序列最大子段。求一维最大子段和函数：
int getMax(int buf[100],int n)
{
int temp[101],max=n*(-127);
memset(temp,0,4*(n+1));

for(int i=1;i<=n;i++)
{
temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
if(max<temp[i])
max=temp[i];
}
return max;
}
下面扩展到二维状况：考察下面题目中例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 7
-1 8 0 -2
咱们分别用i j表达起始行和终结行，遍历所有也许：
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {}
咱们考察其中一种状况 i=2 j=4，这样就相称与选中了2 3 4三行，求那几列组合能获得最大值，由于总是 2 3 4行，因此咱们可以将这3行”捆绑”起来，变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)最大子段和，ok，问题成功转化为一维状况！
带有详细注释代码可以在获得

Pku acm 1014 Dividing 动态规划题目总结(十七)

刚AC了，趁热打铁，写下解题报告，这道题很早就在joj上做过，当时不懂得dp，只会用很菜办法，成果虽然joj这道题仅规定10s还是会超时！
思想：本题是找按价值均分大理石方案与否存在，由于分派时不能破坏大理石，因此有个显而易见剪枝：当所有大理石总价值为奇数时必定不能被均分。把问题转化一下即：由一种人能否从原大理石堆中取出总价值为本来一半大理石,本题重要算法是动态规划,数组flag代表状态,设总价值为sum.当flag[k]==true时，阐明，可以有一人获得价值k,此外一人获得价值V-k大理石分派方案。反之若flag[k]=false阐明这种分派方案不存在.咱们任务就是计算出flag[sum/2]是true还是false，显然有flag[0]==true方案存在，即一种人什么都不分，此外一种人拿走所有大理石.
设i（1<<6）为石头价值，试想若flag[k]==true，如果能再向k中增长一价值为i大理石，则flag[k+i]==true必然成立.石头有两个属性，一种是价值另一种是数量，这里array[i]代表价值为i大理石数量，咱们依照其中一种属性：价值来划分阶段。即for (int i=1;i<=6;i++)，flag[k]表达状态与否存在（这里状态是指能否从原石头堆中分出价值为k新石头堆）。在初始阶段是i=1,初始状态是flag[0]=true,max代表当前满足flag[k]==true这一条件k最大值。
for(int j=max;j>=0;j--) 
//从当前最大值flag开始，依照前面提到flag[j]==true成立则flag[j+i]==true亦成立理论，在原有状态flag[j]==true已存在条件下加入stone[i]阶段石头,得到新状态
还是举个例子吧：3 0 1 2 0 0
flag[] : sum/2=6
i
0
1
2
3
4
5
6
flag[] :
1
0
0
0
0
0
0
对于i=1 array[1] = 3 由于flag[0] = true,因此flag[1]，flag[2]，flag[3]都变为true：
i
0
1
2
3
4
5
6
flag[] :
1
1
1
1
0
0
0
对于i=2 array[2] = 0 不考察
对于i=3 array[3] = 1 由于flag[0] flag[1]，flag[2]，flag[3]= true,因此flag[3]，flag[4]，flag[5]，flag[6]都变为true：
i
0
1
2
3
4
5
6
flag[] :
1
1
1
1
1
1
1
等等等等，咱们任务是判断flag[sum/2]与否为真。
这样程序基本框架就有了：dp函数如下：
bool dp(int array[7])
{
bool flag[60001];
int i,j,k,sum = 0,max=0;
for(i=1;i<=6;i++)
sum += array[i]*i;
if(sum%2!=0)
return false;
memset(flag,0,sizeof(flag));
flag[0] = true;
for(i=1;i<=6;i++)
{
if(array[i]>0)
{
for(j=max;j>=0;j--) //至于为什么要从大到小，写成从小到大，调试一下就可以看出问题，//例如有1个1，本来flag[0] = true,循环一遍后flag[1] = true,此时再判断flag[1]=true,继续flag[2] = true就不//合题意了，从大到小可以解决这个问题
{
if(flag[j])
{
for(k=1;k<=array[i];k++)
{
if(j+k*i==sum/2)
return true;
else if(j+k*i<sum/2&&!flag[j+k*i])
{
if(j+k*i>max) max = j+k*i;
if(j+k*i>sum/2) max = sum/2;
flag[j+k*i] = true;
}
}
}
}
}
}
return false;
}
这样问题就解决了，submit，成果超时，从joj上试了一下，成果ac，6s多，距离poj1s还很远。咱们考察如果flag[j+k*i]已经等于true，就不用继续循环下一种k了，直接break就可以了，详细因素是这样：
假设当前flag[]序列是这样：1 1 0 1 1 0 1 1 0 1，当前考察是 i=3；array[i]=5，就是要在这个基本上加上5个3，按照程序意思，从最后一种1开始依此加上3，将其值变为1，一共加上5个，然后在倒数第二个1上依此加上3，将其值变为1，一共加上5个，这个过程不会碰见flag=1状况，给倒数第三个1依此加3时候，会遇到：flag=1,这个时候就可以break了，由于这时候还需要加4个3都在最后一种1加5个3时候加过了，这里要注意是，给每个1加上3时候，只会遇到”旧”flag=1,不会遇到新增长flag=1,而旧1已经加过了array[i]个i，因此就不用加了，直接退出就行了。
修改后裔码：
for(i=1;i<=6;i++)
{
if(array[i]>0)
{
for(j=max;j>=0;j--)
{
if(flag[j])
{
for(k=1;k<=array[i];k++)
{
if(j+k*i==sum/2)
return true;
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了。0ms。
带有详细注释代码可以在获得

Pku acm 1160 post office 动态规划题目总结(十八)

题目给出m个村庄及其距离，给出n个邮局，规定怎么建n个邮局使代价最小。
思路：用opt[i][j]记录把前i个邮局建到前j个村庄中最优解，用cost[i][j]记录所有在i到j村庄中，建1个邮局最小代价。显然邮局应当设到中点。让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)
Cost数组存储从i到j中有一种邮局最小代价，显然该邮局应当放在中间，构造cost代码和成果如下：
f