DP专题八--石子合并

自用笔记算法

DP专题八–石子合并

任取石子

有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费
最小（或最大）。

分析

当然这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。

蓝桥杯–合并石子

参考90分代码(未优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<algorithm>
#include<cstring>
#include<climits>
#define maxn 1050
using namespace std;
int dp[maxn][maxn];
int n;
int a[maxn],sum[maxn];
void get_min_value()
{
	for(int r=2;r<=n;r++)
	{
		for(int i=1;i<=n-r+1;i++)
		{
			int j=i+r-1;
			int temp=sum[j]-sum[i-1];
			dp[i][j]=dp[i+1][j]+temp;
			cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
			for(int k=i+1;k<j;k++)
			{
				int ans=dp[i][k]+dp[k+1][j]+temp;
				if(ans<dp[i][j])
					dp[i][j]=ans;
				cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
			}
		}
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
			cin>>a[i];
		sum[0]=0;
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+a[i];
		for(int i=1;i<=n;i++)
			dp[i][i]=0;
		get_min_value();
		cout<<dp[1][n]<<endl;
	}
	return 0;
}

参考AC代码(四边形不等式优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
#include<cstring>
#include<climits>
#define maxn 1050
using namespace std;
int dp[maxn][maxn];
int s[maxn][maxn];
int n;
int a[maxn],sum[maxn];
void get_min_value()
{
	for(int r=2;r<=n;r++)
	{
		for(int i=1;i<=n-r+1;i++)
		{
			int j=i+r-1;
			int temp=sum[j]-sum[i-1];
			dp[i][j]=dp[i+1][j]+temp;
			s[i][j]=i;
			/*cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;*/
			for(int k=s[i][j-1];k<=s[i+1][j];k++)
			{
				int ans=dp[i][k]+dp[k+1][j]+temp;
				if(ans<dp[i][j])
				{
					dp[i][j]=ans;
					s[i][j]=k;
				}
				/*cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;*/
			}
		}
	}
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
			cin>>a[i];
		sum[0]=0;
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+a[i];
		for(int i=1;i<=n;i++)
		{
			dp[i][i]=0;
			s[i][i]=i;
		}
		get_min_value();
		cout<<dp[1][n]<<endl;
	}
	return 0;
}

思路

我们熟悉矩阵连乘，知道矩阵连乘也是每次合并相邻的两个矩阵，那么石子合并可以用矩阵连乘的方式来解决。
设dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式：

四边形不等式优化从k的取值从i-j-1优化到s[i][j-1]-s[i+1][j].

POJ 1738–GarsiaWachs算法

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>  
#include <string.h>  
#include <stdio.h>  
using namespace std;  
const int N = 50005;  
int stone[N];  
int n,t,ans;  
void combine(int k)  
{  
	int tmp = stone[k] + stone[k-1];  
	ans += tmp;  
	for(int i=k;i<t-1;i++)  
		stone[i] = stone[i+1];  
	t--;  
	int j = 0;  
	for(j=k-1;j>0 && stone[j-1] < tmp;j--)  
		stone[j] = stone[j-1];  
	stone[j] = tmp;  
	while(j >= 2 && stone[j] >= stone[j-2])  
	{  
		int d = t - j;  
		combine(j-1);  
		j = t - d;  
	}  
}  
int main()  
{  
	while(scanf("%d",&n)!=EOF)  
	{  
		if(n == 0) break;  
		for(int i=0;i<n;i++)  
			scanf("%d",stone+i);  
		t = 1;  
		ans = 0;  
		for(int i=1;i<n;i++)  
		{  
			stone[t++] = stone[i];  
			while(t >= 3 && stone[t-3] <= stone[t-1])  
				combine(t-2);  
		}  
		while(t > 1) 
			combine(t-1);  
		printf("%d\n",ans);  
	}  
	return 0;  
}

思路

对于石子合并问题，有一个最好的算法，那就是GarsiaWachs算法。时间复杂度为O(n^2)。

它的步骤如下：
设序列是stone[]，从左往右，找一个满足stone[k-1] <= stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再从当前位置开始向左找最大的j，使其满足
stone[j] > stone[k]+stone[k-1]，插到j的后面就行。一直重复，直到只剩下一堆石子就可以了。在这个过程中，可以假设stone[-1]和stone[n]是正无穷的。

举个例子：
186 64 35 32 103
因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面，得到：186 67 64 103,现在由5个
数变为4个数了，继续：186 131 103，现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）234 186，最后得到420。最后的答案呢？就是各次合并的重量之和，即
420+234+131+67=852。

基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变。具体
实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化，使得
最终复杂度为O(nlogn)。

HDU 3506–环形石子合并

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cstring>
#include<climits>
#define maxn 2050
using namespace std;
int dp[maxn][maxn],a[maxn],sum[maxn],s[maxn][maxn];
int n;
void get_min_value()
{
	for(int r=2;r<=n;r++)
	{
		for(int i=1;i<=2*n-r+1;i++)
		{
			int j=i+r-1;
			int temp=sum[j]-sum[i-1];
			dp[i][j]=dp[i+1][j]+temp;
			s[i][j]=i;
			/*cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;*/
			for(int k=s[i][j-1];k<=s[i+1][j];k++)
			{
				int ans=dp[i][k]+dp[k+1][j]+temp;
				if(ans<dp[i][j])
				{
					dp[i][j]=ans;
					s[i][j]=k;
				}
				/*cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;*/
			}
		}
	}
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[i][i+n-1]);
	cout<<ans<<endl;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n)
	{
		sum[0]=0;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
			sum[i]=sum[i-1]+a[i];
		for(int i=n+1;i<=(2*n);i++)
			a[i]=a[i-n];
		for(int i=n+1;i<=(2*n);i++)
			sum[i]=sum[i-1]+a[i];
		for(int i=1;i<=(2*n);i++)
		{
			dp[i][i]=0;
			s[i][i]=i;
		}
		get_min_value();
	}
	return 0;
}

思路

与直线型类似 只需把直线扩大两倍即可变为环形
注意更新a和sum数组即可
同意需要注意函数里的j取值为2×n-r+1 非n

本文标题:DP专题八--石子合并

文章作者:Hippopmonkey

发布时间:2017-02-23, 16:49:14

最后更新:2017-02-23, 17:08:34

原始链接:http://xuboming8.github.io/2017/02/23/DP专题八-石子合并/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. DP专题八–石子合并
    1. 1.1. 任取石子
      1. 1.1.1. 分析
    2. 1.2. 蓝桥杯–合并石子
      1. 1.2.1. 参考90分代码(未优化)
      2. 1.2.2. 参考AC代码(四边形不等式优化)
      3. 1.2.3. 思路
    3. 1.3. POJ 1738–GarsiaWachs算法
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
    4. 1.4. HDU 3506–环形石子合并
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
|