本文共 17093 字,大约阅读时间需要 56 分钟。
Pku acm 1163 the Triangle 动态规划题目总结(一)
题目:
对于一个有数字组成的二叉树,求由叶子到根的一条路径,使数字和最大,如:
7
3 8
81 0
27 4 4
4 52 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 动态规划题目总结(二)
Considera 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时,对2的45次方检查,是无法完成的任务。先分析一下这个问题:
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] = 0i=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(inti=0;i<length1;i++){
result[i][0] = 0;
}
for(inti=0;i<length2;i++){
result[0][i] = 0;
}
for(inti=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,newStringBuffer(string).reverse().toString());
//函数LCS返回两个string的lcs的长度
带有详细注释的代码可以在获得
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(inti=0;i<=m;i++){
array[i][0] = i;
}
for(inti=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 OrderedSubsequence 动态规划题目总结(十二)
这个题目和1887 Testing the CATCHER一模一样,没有什么值得说的,关键的c代码如下:
for(i=1;i<=n;i++)
{
for(j=1;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 Subsequence1887 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]
left = mid+1;
else
right = mid-1;
}
opt[i] = left;
B[left] = num;
if(Blen
Blen = left;
if(max
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 23 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]])
{
intnum = 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]>0temp [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(intbuf[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 80 -2
我们分别用i j表示起始行和终止行,遍历所有的可能:
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {}
我们考察其中一种情况 i=2j=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(inti=1;i<=6;i++),flag[k]表示状态是否存在(这里的状态是指能否从原石头堆中分出价值为k的新石头堆)。在初始阶段是i=1,初始状态是flag[0]=true,max代表目前满足flag[k]==true这一条件的k的最大值。 for(intj=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;
elseif(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多,距离poj的1s还很远。我们考察如果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)
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了。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的代码和结果如下:
for(i=1;i<=m;i++)
for(j=i;j<=m;j++)
{
cost[i][j]= 0;
mid= (i+j)/2;
for(k=i;k<=j;k++)
cost[i][j]+=(distance[mid]-distance[k])>=0?
distance[mid]-distance[k]:distance[k]-distance[mid];
}
Cost[i][j] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 0 | 1 | 2 | 6 | 10 | 16 | 21 | 37 | 74 | 117 |
2 | 0 | 1 | 4 | 8 | 11 | 16 | 31 | 68 | 109 | |
3 | 0 | 3 | 4 | 7 | 11 | 26 | 61 | 102 | ||
4 | 0 | 1 | 3 | 7 | 20 | 55 | 94 | |||
5 | 0 | 2 | 4 | 17 | 50 | 89 | ||||
6 | 0 | 2 | 13 | 46 | 74 | |||||
7 | 0 | 11 | 33 | 61 | ||||||
8 | 0 | 22 | 28 | |||||||
9 | 0 | 6 | ||||||||
10 | 0 |
Opt[i][j] 表示前i个邮局覆盖前j个村庄的最小代价,对于i=1来说,opt[i][j] = cost[i][j],让前2个邮局覆盖前j个村庄,也就是i=2的情况,可能是一下情况的最优解:第一个邮局覆盖第一个村庄,第二个村庄覆盖2-j个村庄,或者第一个邮局覆盖第1-2个村庄,第二个村庄覆盖3-j个村庄,第一个邮局覆盖第1-3个村庄,第二个村庄覆盖4-j个村庄,等等等等。该部分的代码如下:
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
if(opt[i][j]<3000000)
{
for(k=1;j+k<=m;k++)
{
if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k])
{
opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k];
}
}
}
Opt[i][j] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
0 | 0 | ||||||||||
1 | 0 | 1 | 2 | 6 | 10 | 16 | 21 | 37 | 74 | 117 | |
2 | 0 | 1 | 4 | 8->5 | 11->8 | 16->12 | 31->27 | 68->62 | 109->103 | ||
3 | |||||||||||
4 | |||||||||||
5 |
带有详细注释的代码可以在获得
Pku acm 1125 Stockbroker Grapevine 动态规划题目总结(十九)
有向图中每一对顶点间的最短路径问题,典型的弗洛伊德算法。
问题描述:已知一个含有n个顶点的各边权值均大于0的带权有向图,对每对顶点vi!=vj,要求求出每一对顶点之间的最短路径和最短路径长度。
解决方案:弗洛伊德(floyd)算法
对于这样一个例子: 4
2
2 52 6
A0[i][j]=cost[i][j]:
A0 | 1 | 2 | 3 |
| A1 | 1 | 2 | 3 |
1 | 0 | 4 | 5 |
| 1 | 0 | 4 | 5 |
2 | 2 | 0 | 6 |
| 2 | 2 | 0 | min(6,2+5) |
3 | 2 | 2 | 0 |
| 3 | 2 | min(2,2+4) | 0 |
A2 | 1 | 2 | 3 |
| A3 | 1 | 2 | 3 |
1 | 0 | 4 | min(5,4+6) |
| 1 | 0 | min(4,5+2) | 5 |
2 | 2 | 0 | 6 |
| 2 | min(2,6+2) | 0 | 6 |
3 | min(2,2+2) | 2 | 0 |
| 3 | 2 | 2 | 0 |
核心的c代码如下:
for(int k=1;k<=n;k++) //生成A0,A1,A2...的循环
for(inti=1;i<=n;i++) //行
for(int j=1;j<=n;j++) //列
//如果是i==k||j==k||i==j就保持不变,否则取最小值
array[i][j]=(i==k||j==k||i==j)?array[i][j]:
((array[i][j]<(array[i][k]+array[k][j])?array[i][j]:(array[i][k]+array[k][j])));
最后根据题意,取每行最大值中的最小值即可。
带有详细注释的代码可以在获得
Pku acm 1179 Polygon动态规划题目总结(二十)
多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步,将一条边删除。
随后n-1步按以下方式操作:
(1)选择一条边E以及由E连接着的2个顶点V1和V2;
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。
问题:对于给定的多边形,计算最高得分。分析:
• 在所给多边形中,从顶点i(1≤i≤n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j) 可表示为v[i],op[i+1],…,v[i+j-1]。
• 如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1),则可在op[i+s]处将链分割为2个子链p(i,s)和p(i+s,j-s)。
• 设m1是对子链p(i,s)的任意一种合并方式得到的值,而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一种合并方式得到的值,而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b,c≤m2≤d
(1)当op[i+s]='+'时,显然有a+c≤m≤b+d
(2)当op[i+s]='*'时,有min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}
• 换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。
这道题收获非常多:
1.已经定义了变量max,然后调用一个已经定义的函数max时报错:term does not evaluate to a function,原因是之前定义了一个int max;所以max(a,b)是把变量错误的当作函数使用
2.由于是一个环,所以下标要对n取模,这里还有一个技巧,例如当n=4时,4对4取模为0,不合要求,所以应该减一取模后加一
3.该例输入为:
4
t -7 t 4 x 2 x 5
开始输入语句为:
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%c",&edge[i]);
scanf("%d",&vertex[i]);
}
读入了很多空格,因为空格也是char,然后修改为:
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%c",&edge[i]);
scanf("%d",&vertex[i]);
if(i!=n)
scanf("%c",&edge[0]);
}
就是如果不是最后一个数字,读取数字后读取一个空格,然而这个时候还是无法正常读入,因为4后面有一个换行,被错误的读入到edge[1]中,所以在读取4是加一个\n
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
scanf("%c",&edge[i]);
scanf("%d",&vertex[i]);
if(i!=n)
scanf("%c",&edge[0]);
}
最后改为了:
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
scanf(" %c",&edge[i]);
scanf("%d",&vertex[i]);
}
4.提交后 Time LimitExceeded
发现代码中竟然有:
this_max =Max(getMaxResult(vertexth,i-1,true)*getMaxResult((vertexth+i-1)%n+1,length-i,true), getMaxResult(vertexth,i-1,true)*getMaxResult((vertexth+i-1)%n+1,length-i,false),
getMaxResult(vertexth,i-1,false)*getMaxResult((vertexth+i-1)%n+1,length-i,true),
getMaxResult(vertexth,i-1,false)*getMaxResult((vertexth+i-1)%n+1,length-i,false));
这种语句,不Time Limit Exceeded 就奇怪了,接着改为:用变量保存结果,然后取最大值:
int firstTrue = getMaxResult(vertexth,i-1,true);
int secondTrue = getMaxResult((vertexth+i-1)%n+1,length-i,true);
int firstFalse = getMaxResult(vertexth,i-1,false);
int secondFalse = getMaxResult((vertexth+i-1)%n+1,length-i,false);
this_max =Max(firstTrue*secondTrue,firstTrue*secondFalse,firstFalse*secondTrue,firstFalse*secondFalse);
5.结果还是 Time Limit Exceeded 然后想到 可能多次求一个
getMaxResult,比如可能多次求一个getMaxResult(3,4,true),所以应该将结果保存起来,这正是动态规划的本质!刘汝佳《算法艺术和信息学竞赛》中115页讲到技艺化搜索,这个例子就非常典型。定义一个3维数组,然后初始化为一个很小的值,然后调用getMaxResult时先判断是不是已经计算过了(就是数组中是不是已经有值了),如果计算过就直接返回,否则在返回之前将值保存到数组中!
结果AC 帅,15ms
带有详细注释的代码可以在获得
by 苏强(neuq&jlu)
2008-1-1
转载地址:http://qtyhj.baihongyu.com/