[NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将堆石子合并成堆的最小得分和最大得分。

输入格式

数据的第行是正整数，表示有堆石子。

第行有个整数，第个整数表示第堆石子的个数。

输出格式

输出共行，第行为最小得分，第行为最大得分。

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

，。

题解

弱化版（不考虑环）

我们简单看一下题目，要我们合并石子，很容易想到的结论就是两堆石子数目小的话合并所需的得分就小，两堆石子数目大的话合并所需要的得分就大，这里可能容易跟另一道名叫“合并果子”的著名贪心题目搞混，这里注意一下，由于我们是每次合并的时候只能使用相邻的两堆石子，跟他们的相对顺序有关，贪心很显然是错的，因此这道题目我们使用动态规划来解决。

对于一个第 L 堆石子到第 R 堆石子，我们考虑这堆石子的合并所需要的最小的分从何而来。很显然，L~R 这堆石子的最小得分一定是从这个区间中两个某子区间的最小得分转移而来，因此我们可以考虑枚举这两个子区间，这样一来我们可以得到下面的方程式：

我们设表示第堆石子到第堆石子的最小得分，我们枚举子区间的分割点，那么有:
$到的石子数到的石子数$

上面的式子就是我们本题的状态转移方程式,最后就是答案，求最大值的话就是 min 改成 max 就行了，~~但是本题难点不在于这个（~~，我们还有两个悬而未决的问题：

转移的顺序如何确定
题目中说的是圆形操场，因此这堆石子其实是一个环，即第 1 堆石子可以和第 n 堆合并

先解决第一个问题，我们可以想象一下，对于一个大区间，他肯定是从两个比它小的区间转移而来，因此我们要按区间长度从小到大计算。

其实对于这类转移顺序不好确定问题，我们可以使用记忆化搜索的形式来编写代码，可以巧妙的规避这个问题。

我们要枚举 l,r,k 同时还要计算区间和,每一个计算都要 o(n)的时间复杂度，因此我们总的时间复杂度是，~~包超时的老弟~~,我们可以使用前缀和来优化掉 O(n) 的区间求和，这样我们的时间复杂度就可以到，这样就不会超时。

代码如下(非记忆化搜索),对应”洛谷 P1775 石子合并（弱化版）”

MAXN = 1005
f = [[9999999999] * MAXN for i in range(MAXN)]
n = int(input())
m = list(map(int,input().split()))
m.insert(0,0)
# 算代价
s = [0] * (n + 10)
for i in range(1,n+1):
    s[i] = s[i-1] + m[i]
def sum(l,r):
    return s[r] - s[l-1]

for i in range(1,n+1):
    f[i][i] = 0
for length in range(1,n+1):
    for l in range(1,n-length+2):
        r = l + length - 1
        for mid in range(l,r):
            f[l][r] = min(f[l][r],sum(l,r) + f[l][mid] + f[mid + 1][r])
print(f[1][n])

标准版（考虑环）

上面是这个题目的弱化版的代码，接下来我们考虑如何将这个区间变成环，一个很简单的做法 ~~（但是不好想）~~ 就是我们将原始的石子复制两遍让他们首尾相接，之后正常转移，最后在 1~2n 的区间中寻找长度为 n 的石子最优解就可以了。

代码如下

MAXN = 1005
f = [[9999999999] * MAXN for i in range(MAXN)]
g = [[0] * MAXN for i in range(MAXN)]
n = int(input())
a = list(map(int,input().split()))
# 算代价
for i in range(n):
    a.append(a[i])
a.insert(0,0)
s = [0] * (2 * n+ 10)
for i in range(1,2 * n+1):
    s[i] = s[i-1] + a[i]
def sum(l,r):
    return s[r] - s[l-1]

for i in range(1,2 * n+1):
    f[i][i] = 0
    g[i][i] = 0
for length in range(1,n+1):
    for l in range(1,2 * n-length+2):
        r = l + length - 1
        for mid in range(l,r):
            f[l][r] = min(f[l][r],sum(l,r) + f[l][mid] + f[mid + 1][r])
            g[l][r] = max(g[l][r], sum(l, r) + g[l][mid] + g[mid + 1][r])
min_ans = 999999
max_ans = 0
for i in range(0, n+1):
    min_ans = min(min_ans, f[1+i][n+i])
    max_ans = max(max_ans, g[1+i][n+i])
print(str(min_ans) + "\n" + str(max_ans))

下面放一下另一种写法，C++版的记忆化搜索版代码

#include<algorithm>
#include<iostream>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans1,ans2;
int a[205],f1[205][205],f2[205][205];
int dp1(int L,int R) {
    if(f1[L][R])return f1[L][R];
    if(L==R)    return f1[L][R]=0;
    int res=INF;
    for(int k=L; k<R; k++)
        res=min(res,dp1(L,k)+dp1(k+1,R)+a[R]-a[L-1]);
    return f1[L][R]=res; }
int dp2(int L,int R) {
    if(f2[L][R])return f2[L][R];
    if(L==R)    return f2[L][R]=0;
    int res=0;
    for(int k=L; k<R; k++)
        res=max(res,dp2(L,k)+dp2(k+1,R)+a[R]-a[L-1]);
    return f2[L][R]=res; }
int main() {
    ios::sync_with_stdio(false);
    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];
    dp1(1,2*n);
    dp2(1,2*n);
    ans1=INF;
    ans2=0;
    for(int i=1; i<=n; i++) {
        ans1=min(f1[i][n+i-1],ans1);
        ans2=max(f2[i][n+i-1],ans2); }
    cout<<ans1<<endl<<ans2;
    return 0; }

Shineria's Blog

洛谷P1880 [NOI1995] 石子合并题解