[题解] LOJ – 10147 石子合并

题目描述

将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：
1. 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最小。

输入格式

输入第一行一个整数 $n$，表示有 $n$ 堆石子。
第二行 $n$ 个整数，表示每堆石子的数量。

输入格式

输出共两行：
第一个为合并得分总和最小值，
第二行为合并得分总和最大值。

样例输入

4
4 5 9 4

样例输出

43
54

数据范围及提示

对于 $100 \%$的数据，有 $1 \leq n \leq 200$

时空限制

时间限制：1s
空间限制：512MB

解题分析

区间 $DP$ 入门经典题，因为是一个环形的操作，所以我们将数组复制一遍再进行 $DP$，最后用每一个长度为 $n$ 的段统计答案

令数组 $f[l][r]$ 表示第 $l$ 到 $r$ 堆石子合并为一堆总分的最小值

令数组 $g[l][r]$ 表示第 $l$ 到 $r$ 堆石子合并为一堆总分的最大值

$$f[l][r] = min(f[l][k], f[k][r]) + \sum_{i=l}^{r} a_i $$

$$g[l][r] = max(g[l][k], g[k][r]) + \sum_{i=l}^{r} a_i $$

再用一个前缀和维护区间和即可

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 400 + 10;
const int INF = 0x3f3f3f3f;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int data[MAXN];

int f[MAXN][MAXN];
int g[MAXN][MAXN];

int sum[MAXN];
int n;

int maxn = -INF;
int minn = INF;

int main(){
    n = read();

    for(register int i=1; i<=n; i++){
        data[i] = data[n+i] = read();
    }

    for(register int i=1; i<=2*n; i++){
        sum[i] = sum[i-1] + data[i];
    }

    for(register int len=2; len <= n; len++){
        for(register int l = 1; l <= 2*n - len + 1; l++){
            int r = l + len - 1;

            f[l][r] = INF;
            g[l][r] = -INF;

            for(register int k=l; k<r; k++){
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]);
                g[l][r] = max(g[l][r], g[l][k] + g[k+1][r]);
            }

            f[l][r] += sum[r] - sum[l-1];
            g[l][r] += sum[r] - sum[l-1];
        }
    }

    for(register int i=1; i<=n; i++){
        maxn = max(maxn, g[i][i+n-1]);
        minn = min(minn, f[i][i+n-1]);
    }

    printf("%d\n", minn);
    printf("%d", maxn);

    return 0;
}