题目

• 原题地址：石子合并
• 题目编号：NC50493
• 题目类型：DP、区间DP
• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 32768K，其他语言65536K

1.题目大意

• 将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
• 请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算：
  • 选择一种合并石子的方案，使得做n-1次合并得分总和最大。
  • 选择一种合并石子的方案，使得做n-1次合并得分总和最小。

2.题目分析

• 区间DP是先枚举长度，再枚举起点，然后在起点和终点之间枚举中间点，表示合并的两个区间。

3.题目代码

#include <bits/stdc++.h>
#define N 1000

using namespace std;

int n,a[N],f[N][N],g[N][N],l,r;
int main() {
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i], a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) a[i] += a[i-1];
    for(int i=2;i<=n;i++)
        for(l=1;l<=2*n-i+1;l++){
            r = l + i - 1, g[l][r] = 1e8;
            for(int j=l;j<r;j++){
                f[l][r] = max(f[l][r],f[l][j]+f[j+1][r]+a[r]-a[l-1]);
                g[l][r] = min(g[l][r],g[l][j]+g[j+1][r]+a[r]-a[l-1]);
            }
        }
    l = 1e8, r = 0;
    for(int i=1;i<=n;i++){
        l = min(l,g[i][i+n-1]);
        r = max(r,f[i][i+n-1]);
    } cout << l << endl << r << endl;
}