蓝桥杯 算法提高-合并石子(区间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;
}
上一篇: OpenGL入门之使用EBO绘制四边形
下一篇: DP(优化专题-四边形不等式优化一)