题解 P1880 【[NOI1995]石子合并】
你是不是还因为比样例大1而苦恼
你是不是还因为前缀和而焦虑
不要 9998 不要 998 只要 996
让某菌来拯救样例MIN值是44的苍生吧
言归正传
题目
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分。
首先可以轻松排除贪心的可能
分析
这道题肯定要用区间DP
我们先只考虑直线的情况
假设只有2堆石子,显然只有1种合并方案
如果有3堆石子,则有2种合并方案,((1,2),3)和(1,(2,3))
如果有4堆石子,则有5种合并方案
(((1,2),3),4)、((1,(2,3)),4)、(1,((2,3),4))、(1,(2,(3,4)))、((1,2),(3,4))
如果有k堆石子呢?
不管怎么合并,总之最后总会归结为2堆,如果我们把最后两堆分开,左边和右边无论怎么合并,都必须满足最优合并方案,整个问题才能得到最优解。如下图
codevs上有一道题:1048 石子归并
题目是
有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。
分析
设f[i][j]:区间[i,j]合并成一堆的最优值
可以推出动态规划方程为f[i][j]=f[i][k]+f[k+1][j]+cost[i,j]
阶段:len: 2 ~ n
状态:i: 1 ~ n – len + 1, j: i + len – 1
策略:k: i ~ j
所以时间复杂度为n^4
优化:预处理sum[i]表示前i堆石子总数量,则cost[i,j] = sum[j] – sum[i - 1],时间优化为n^3
分析图
鼠标作图极丑
恰好就可以打出如下代码
/*
作者:dayuanjun
题目:p1048 石子归并
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int w[105];
int f[105][105];
int cost[105][105];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)
{
cost[i][j]+=w[k];
}
for(int i=1;i<=n;i++)
{
f[i][i]=0;
}
for(int len=2;len<=n;len++)
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
}
}
printf("%d",f[1][n]);
return 0;
}
然而这道题是一个环
所以
加上环怎么办?
断环为链:将长度为n的链复制一份接在后面,环的情况就是长度为2n的链中任意连续的长度为n的链。
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[i+n]=w[i];
}
因为要求最大值,所以再开一个数组存最大值
#include<bits/stdc++.h>
using namespace std;
int n;
int w[205];
int f[205][205];
int ff[205][205];
int cost[205][205];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[n+i]=w[i];
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=i;k<=j;k++)
{
cost[i][j]+=w[k];
}
for(int i=1;i<=n;i++)
{
f[i][i]=0;
ff[i][i]=0;
}
for(int len=2;len<=n;len++)
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
}
}
int ans1=0x7fffffff/2,ans2=0;
for(int i=1;i<=n;i++) ans1=min(ans1,f[i][i+n-1]);
for(int i=1;i<=n;i++) ans2=max(ans2,ff[i][i+n-1]);
printf("%d\n%d",ans1,ans2);
return 0;
}
然而 少年你天真了 颜色逐渐蒟蒻化
修改 ※
我们要注意,因为加了一圈,所以求前缀和的for循环不应该是1~n了,而应该是1~2n,如下
for(int i=1;i<=2*n;i++)
for(int j=i;j<=2*n;j++)
for(int k=i;k<=j;k++)
{
cost[i][j]+=w[k];
}
同时在DP部分l也要循环到2*n
for(int len=1;len<n;len++)
for(int l=1,r=l+len;r<n*2&&l<n*2;l++,r=l+len)
{
f[l][r]=0x7fffffff/2;
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
}
}
代码如下
#include<bits/stdc++.h>
using namespace std;
int n;
int w[205];
int f[205][205];
int ff[205][205];
int cost[205][205];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[n+i]=w[i];
}
for(int i=1;i<=2*n;i++)
for(int j=i;j<=2*n;j++)
for(int k=i;k<=j;k++)
{
cost[i][j]+=w[k];
}
for(int i=1;i<=n;i++)
{
f[i][i]=0;
ff[i][i]=0;
}
for(int len=1;len<n;len++)
for(int l=1,r=l+len;r<n*2&&l<n*2;l++,r=l+len)
{
f[l][r]=0x7fffffff/2;
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
}
}
int ans1=0x7fffffff/2,ans2=0;
for(int i=1;i<=n;i++) ans1=min(ans1,f[i][i+n-1]);
for(int i=1;i<=n;i++) ans2=max(ans2,ff[i][i+n-1]);
printf("%d\n%d",ans1,ans2);
return 0;
}
知乎 大源菌
b站源菌想吃木桶饭