欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 算法提高-合并石子(区间dp)

程序员文章站 2022-04-01 18:42:34
...

题目

在一条直线上有n堆石子,每堆有一定的数量,

每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,

合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。

1<=n<=1e3,1<=ai<=1e4

思路来源

https://blog.csdn.net/noiau/article/details/72514812

心得

寒假看懂了这个的证明,现在又不会证了,那现在就记结论吧

回头等蓝桥杯结束之后,再写篇长文证明一下(咕咕咕)

 

①l降r增,外l内r

记成左负右正,外厉内荏叭hhhh记忆力不好

②pos[l][r]属于[pos[l][r-1],pos[l+1][r]],

左负右正外厉内荏前减后加重要的结论念三遍

 

满足区间dp四边形不等式的时候,

后面加的那个东西只与l和r有关,而与k无关才可,否则不能用

矩阵乘法那个题目,企图用四边形不等式,然后GG了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e3+5;
int n;
int a[maxn],sum[maxn];
int pos[maxn][maxn];
ll dp[maxn][maxn];
int main()
{
	while(~scanf("%d",&n))
	{
	for(int i=1;i<=n;++i)
	{
	scanf("%lld",&a[i]);
	sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			if(i==j)dp[i][j]=0,pos[i][j]=i;
			else dp[i][j]=1e18;
		}
	}
	//l降序 r增序 
	for(int l=n;l>=1;--l)
	{
		for(int r=l+1;r<=n;++r)
		{
			ll tmp=1e18,ans;
			for(int k=pos[l][r-1];k<=pos[l+1][r];++k)
			{
				ll res=dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1];
				if(tmp>res)
				{
					tmp=res;
					ans=k;
				}
			}
			dp[l][r]=tmp;
			pos[l][r]=ans; 
		}
	}
	printf("%lld\n",dp[1][n]);
    }
	return 0;
}