DengDuckのBlog

合并石子三讲

发布于 2021-09-05 | 标签: 题目解法 、 算法总结 | 17分钟 | 3559字数

本文讲介绍关于合并石子的做法：

区间DP，记忆化搜索和四边形不等式优化

题目大意：

设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N

每堆石子有一定的质量，可以用一个整数来描述

现在要将这 NN 堆石子合并成为一堆，每次只能合并相邻的两堆

合并的代价为这两堆石子的质量之和

合并后与这两堆石子相邻的石子将和新堆相邻

合并时由于选择的顺序不同，合并的总代价也不相同

找出一种合理的方法，使总的代价最小，输出最小代价

同时输出合并过程

合并石子其实和 合并果子
很像

只是合并 只能相邻，但其实也方便了 区间dp

从最后一次合并开始思考

最后一次合并前，石子肯定只有两堆 ，

设k为两者 中点 ， 也就是两堆中间的位置

第一堆是原来的11到kk堆，第二堆是原来的第k+1k+1到第nn堆。

显然，

要使得总代价最小，必然是该两堆式子之前的合并代价最小。

然后不断拆分成子问题解决

定义状态f(i,j)f(i,j)

表示 第i堆石子到第j堆石子 的 最小合并代价 。

目标状态即为f(1,n)f(1,n)。

方程——f(i,j)=min(f(i,k)+f（k+1,j)+sum(i,j)f(i,j)=min(f(i,k)+f（k+1,j)+sum(i,j)

sum是什么呢？是一个 区间和 ，我们利用 前缀和 可以将询问sum的复杂度降至 O(1)

int query(int i, int j) //前缀和，sum[i],表示1~i的和，数学内容，简单，自行思考原理 
{ 
	return sum[j] - sum[i - 1]; 
}

为什么是 区间和 呢？

其实 区间和就是两堆的重量（简单，自行思考）

也就是 合并代价

然后是 初始化

因为是求最小值，所以要开一个大数

memset(f, 27, sizeof(f));

27其实计算机会认为是一个很大的数，接近int边界，并不是我们认为的27

也可以换成其他数

    for (int i = 1; i <= n; i++) 
	{
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];// 预处理前缀和
        f[i][i] = 0;//自己合并自己不需要代价 
    }

输入可以同时处理

见代码，sum可以求，因为自己合并自己不需要代价 ，所以f(i,i)f(i,i)始终为0

接下来讲解dp部分

由于我们已经知道起点和区间大小，所以可以求终点

然后枚举中点就完了

    for (int k = 2; k <= n; k++)//k,枚举区间大小 
	{ 这个p是什么呢？

p数组用来记录最优解的中点 

Why？


        for (int i = 1; i <= n; i++) //i,枚举起点 
		{
            int j = i + k - 1;//求终点 
            for (int l = i; l < j; l++)//枚举中点，这里可以优化，详见PPT《DP之四边形不等式优化》 
			 {
                if (f[i][j] > f[i][l] + f[l + 1][j] + query(i, j)) //求最小值 
				{
                    f[i][j] = f[i][l] + f[l + 1][j] + query(i, j);
                    p[i][j] = l;//有新的最小值,更新中点 
                }
            }
        }
    }

这个p是什么呢？

p数组用来记录最优解的中点

Why？

由于题目要求过程，我们可以用递归求解

这时p就派上用场了

p(i,j)p(i,j)表示合并i,j时的中点k

由此将l,r分成两份，不断递归


void dg(int l, int r) 
{
    if (l == r) {//说明只有一个数，直接输出！ 
        cout << a[r];//不要换行！不要空格！ 
        return;
    }
    cout << '(';//输出左右括号 
    int mid = p[l][r];//读取中点 
    dg(l, mid);//递归左半部分 
    cout << ")(";//输出中间括号 
    dg(mid + 1, r);//递归右半部分
    cout << ')';//输出左右括号 
}

好了，这就是关于合并石子的全部内容了

上代码！

#include <bits/stdc++.h>
using namespace std;
int n, a[1005], f[1005][1005], p[1005][1005], sum[1005];
int query(int i, int j) 
{ 
	return sum[j] - sum[i - 1]; 
}
void dg(int l, int r) 
{
    if (l == r) {
        cout << a[r];
        return;
    }
    cout << '(';
    int mid = p[l][r];
    dg(l, mid);
    cout << ")(";
    dg(mid + 1, r);
    cout << ')';
}
int main() {
    memset(f, 27, sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; i++) 
	{
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        f[i][i] = 0;
    }
    for (int k = 2; k <= n; k++)
	{ 
        for (int i = 1; i <= n; i++) 
		{
            int j = i + k - 1;
            for (int l = i; l < j; l++)
			 {
                if (f[i][j] > f[i][l] + f[l + 1][j] + query(i, j)) 
				{
                    f[i][j] = f[i][l] + f[l + 1][j] + query(i, j);
                    p[i][j] = l;
                }
            }
        }
    }
    cout << f[1][n] << endl; 
    dg(1, n);
    return 0;
}

记忆化搜索更加清晰，易于理解

(不过无法使用四边形不等式优化)

浅谈记忆化：

如果说动态规划是递推，那记忆化就是递归

它的思路是：

同动态规划，若子问题的解永远不变，再次计算便没有意义

我们将其记录在 f 数组或dp数组（命名习惯不同）

但动态规划算出了所有子问题

所以，我们用递归求解，保证只求到有用子问题

但其实因为递归实现，二者复杂度接近，动态规划较快

它的框架是：

类型 dg(参数)
{
    if(f[参数]已经计算过)return f[参数];
    if(边界)return 对应的数;  //如果已经给边界初始化，可以省略
    计算 
    f[参数]=解//保存解
    return 解;
}

注意！使用递归函数表示子问题！

代码详解：

memset(f,-1, sizeof(f));
n = read();//又 用 快 读
for (int i = 1; i <= n; i++) {
    a[i] = read();
    p[i][i]=i;
}

输入，初始化

注意！f = -1 表示 未计算！

前缀和略

printf("%ld\n", dg(1, n));//输出解
dfs(1, n);//求过程

主函数完

求过程略

记忆化部分和动态规划很像，因为我们知道了起点i和终点j

所以处理完边界后，可以直接枚举中点

long dg(int i, int j) 
{
    if(i==j)return 0;//边界，自己合并自己不需要代价
    if (f[i][j] != -1) //如果计算了，返回
	{
        return f[i][j];
    }
    f[i][j]=1E9;
    for (int k = i; k <= j; k++) //计算
	{
        if (f[i][j] > dg(i, k) + dg(k + 1, j) + w(i, j)) //注意!用dg表示子问题！
		{
            f[i][j] = dg(i, k) + dg(k + 1, j) + w(i, j);
            p[i][j] = k;//记录中点
        }
    }
    return f[i][j];//返回
}

上代码：

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int ans = 0;
    char c = getchar();
    while ((c < '0' || c > '9') && (c != '-')) {
        c = getchar();
    }
    ans = c - '0';
    c = getchar();
    while (c >= '0' && c <= '9') {
        ans = (ans << 3) + (ans << 1) + c - '0';
        c = getchar();
    }
    return ans;
}
long f[105][105], p[105][105], a[105], sum[105], n, mn = 1E9;
long w(long i, long j)
{
	return sum[j] - sum[i - 1]; 
}
void dfs(int l, int r) {
    if (l == r) {
        cout << a[r];
        return;
    }
    cout << '(';
    int mid = p[l][r];
    dfs(l, mid);
    cout << ")(";
    dfs(mid + 1, r);
    cout << ')';
}
long dg(int i, int j) 
{
    long x, y;
    if(i==j)return 0;
    if (f[i][j] != -1) 
	{
        return f[i][j];
    }
    f[i][j]=1E9;
    for (int k = i; k <= j; k++) 
	{
        if (f[i][j] > dg(i, k) + dg(k + 1, j) + w(i, j)) 
		{
            f[i][j] = dg(i, k) + dg(k + 1, j) + w(i, j);
            p[i][j] = k;
        }
    }
    return f[i][j];
}
int main() {
    memset(f,-1, sizeof(f));
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        p[i][i]=i;
	}
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    printf("%ld\n", dg(1, n));
    dfs(1, n);
}

题目大意：

在一圆形操场四周摆放N堆石子 , 现要将石子有次序地合并成一堆.

规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。

编一程序,选择一种合并石子的方案,使得做N-1次合并,得分的总和最少

但数据高达n<=2500

知识讲解：

在动态规划问题中，有一个常见的状态转移方程：

f(i,j)=min(f(i,k)+f(k+1,j))+w[i,j]f(i,j)=min(f(i,k)+f(k+1,j))+w[i,j]

注意上面的粗体部分

min——求最小值

k——枚举的中点
w[i,j]w[i,j]——一个区间处理的函数（如前缀和）

这种公式就是将一个问 题 通过 一个枚举的中点将问题拆成两半，然后加上一个其他利益的计算函数

这种公式若有这三个元素，可以如下判断：

w[i,j]w[i,j]是否满足两个性质：

1.若i<i’<j<j’i<i’<j<j’,则w[i′,j]<=w[i,j′]w[i',j]<=w[i,j']——区间包含

解析 ：其实很好理解，整个区间是w[i,j′],w[i′,j]w[i,j'],w[i',j]是里面的小区间，我们判断时只要看整体里的小区间是否一定小于整体区间即可

如：区间和就是一个区间包含，比如sum（1,6)sum（1,6)一定大于sum(2,4)sum(2,4)

2.若i<i’<j<j’i<i’<j<j’,则w(i,j)+w(i′,j′)<=w(i,j′)+w（i′,j)w(i,j)+w(i',j')<=w(i,j')+w（i',j)——平行四边形不等式。

为什么叫平行四边形不等式？我不知道

但是我们大概记一下即可

可以证明：若w满足区间包含单调性和平行四边形不等式，则f也满足区间平行四边形不等式的性质。

不用记证明，我们记结论

设s(i,j)表示f(i,j)的最佳决策点

也就是f (i,j)为最小值时的中点k

则s满足

{​s(i−1)(j)<=s(i,j)<=s(i)(j+1)​s(i)(j−1)<=s(i,j)<=s(i+1)(j)\begin{cases} ​ s(i-1)(j)<=s(i,j)<=s(i)(j+1)\\ ​ s(i)(j-1)<=s(i,j)<=s(i+1)(j) \end{cases}

但只适用于求min

想一想，为什么？

答案将在树的构造的题解公布

这样，我们可以减少枚举的次数

显然，k的最优解=s(i,j)s(i,j)

范围缩小了

因为我们求s(i,j)s(i,j),

一定需要s(i−1)(j)，s(i)(j+1)s(i-1)(j)，s(i)(j+1)

或者s(i)(j−1)，s(i+1)(j)s(i)(j-1)，s(i+1)(j)

所以我们需要选择，

两个不等式，需一个i从大到小枚举，需一个j从大到小枚举

Ps：我们要判断s是否为零，如果为零就仍用i~j

蒟蒻讲的可能不标准，详见PPT

题目详解：

合并石子公式：f(i,j)=min(f(i,l)+f(l+1,j)+w(i,j))f(i,j)=min(f(i,l)+f(l+1,j)+w(i,j))

具有三要素

w(i,j)w(i,j)为区间和

满足 区间包含单调性和平行四边形不等式

可以用平行四边形不等式优化

j是由i计算的，所以使用i从大到小的 s(i)(j−1)<=s(i,j)<=s(i+1)(j)s(i)(j-1)<=s(i,j)<=s(i+1)(j)

代码详解：

大多数和版本二相同

输入和初始化：

	n=read();//又用了快读，我是有病吗？
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i+n]=read();//输入a
		f[i][i]=f[i+n][i+n]=0;//初始化f
		s[i][i]=i;//分割自己，自己是自己的中点，故s[i][i]=i
		s[i+n][i+n]=i+n;//同上
	}
	n*=2;

对了，这是个环，但做了版本二后环已经废了，就是来加大数据的

求前缀和（略）

DP部分

没什么注意的

重点是i从大到小

	for(int k=2;k<=n/2;k++)//区间大小
	{
		for(int i=n-k+1;i>=1;i--)//从大到小枚举起点
		{
			int j=i+k-1,x,y;//求终点
			if(s[i][j-1])//如果s(i,j-1)为0，从i开始
			{
				x=s[i][j-1];
			}
			else
			{
				x=i;
			}
			if(s[i+1][j])//如果s(i+1,j)为0，从j结束
			{
				y=s[i+1][j];
			}
			else
			{
				y=j;
			}			
			for(int l=x;l<=y;l++)//同版本二
			{
				if(f[i][j]>f[i][l]+f[l+1][j]+w(i,j))
				{
					f[i][j]=f[i][l]+f[l+1][j]+w(i,j);
					s[i][j]=l;
				}
			}
		} 		
	}

因为有多种可行方案，所以我们循环要找一个min

	for(int i=1;i<=n/2;i++)
	{
		mn=min(mn,f[i][i+n/2-1]);
	}

输出即可

上代码：

没忍住打了个快读

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

inline int read() 
{
    int ans = 0;
    char c = getchar();
    while ((c < '0' || c > '9') && (c != '-'))
	{
		c = getchar();
	}
    ans = c - '0';
	c = getchar();
    while (c >= '0' && c <= '9') 
	{
		ans = (ans << 3) + (ans << 1) + c - '0';
		c = getchar();
	}
    return ans;
}
long f[5005][5005],s[5005][5005],a[5005],sum[5005],n,mn=1E8;
long w(long i,long j)
{
	return sum[j]-sum[i-1];
}
int main()
{
	memset(f,127,sizeof(f));
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i+n]=read();
		f[i][i]=f[i+n][i+n]=0;
		s[i][i]=i;
		s[i+n][i+n]=i+n;
	}
	n*=2;
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i];
	}
	for(int k=2;k<=n/2;k++)
	{
		for(int i=n-k+1;i>=1;i--)
		{
			int j=i+k-1,x,y;
			if(s[i][j-1])
			{
				x=s[i][j-1];
			}
			else
			{
				x=i;
			}
			if(s[i+1][j])
			{
				y=s[i+1][j];
			}
			else
			{
				y=j;
			}			
			for(int l=x;l<=y;l++)
			{
				if(f[i][j]>f[i][l]+f[l+1][j]+w(i,j))
				{
					f[i][j]=f[i][l]+f[l+1][j]+w(i,j);
					s[i][j]=l;
				}
			}
		} 		
	}	
	for(int i=1;i<=n/2;i++)
	{
		mn=min(mn,f[i][i+n/2-1]);
	}
	printf("%d",mn);
}

---------- 本文到此结束 感谢您的阅读 ----------

赞赏
  • 本文作者： DengDuck
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
题目解法 算法总结

2021年9月20日模拟赛总结 上一篇
网站已安全运行：
总访问量： 次 | 总访客数： 人
非常好博客，爱来自鸭子！
希望大家喜欢我的博客和DuckOI
0%