Luogu P1880 [NOI1995]石子合并 题解
请先掌握区间dp。
题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1：
1 | 4 |
输出样例#1：
1 | 43 |
典型的环形dp题。
思路见注释。
代码：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
using namespace std;
int a[110],f[110][110][2],n,ma,mi;
//用f[i][j][0]表示合并从i到j的最小花费，f[i][j][1]表示合并从i到j的最大花费
int sum(int i,int j)
{
int ans=0;
while(i<=j) ans+=a[i++];
return ans;
}//计算合并从i到j（含i和j）的总费用
void solve()
{
for(int t=1;t<n;t++)
{
for(int i=0;i<n-t;i++)
{
int j=i+t;
f[i][j][0]=INF;
f[i][j][1]=-INF;
int tmp=sum(i,j);
for(int k=i;k<j;k++)
{
if(f[i][j][0]>f[i][k][0]+f[k+1][j][0]+tmp) f[i][j][0]=f[i][k][0]+f[k+1][j][0]+tmp;
if(f[i][j][1]<f[i][k][1]+f[k+1][j][1]+tmp) f[i][j][1]=f[i][k][1]+f[k+1][j][1]+tmp;
}
}
}
mi=minn(mi,f[0][n-1][0]);
ma=maxn(ma,f[0][n-1][1]);
}
int main()
{
cin>>n;
ma=-INF;mi=INF;//初始化最大值为极小值，最小值为极大值
memset(f,0,sizeof(f));
for(int i=0;i<n;i++) scanf("%d",&a[i]);
solve();//先按原顺序计算一遍
for(int i=1;i<n;i++)
{
memset(f,0,sizeof(f));
int tmp=a[0];
for(int j=0;j<n-1;j++) a[j]=a[j+1];
a[n-1]=tmp;//第一个数移到最后，其余每个数向前移动一位
solve();//重算
//环形dp的重点在于变更原有顺序重算
}
cout<<mi<<endl<<ma;
return 0;
}