NOI1995 石子合并 [Luogu P1880]

一道区间dp的模板题，这里主要记一下dp时环形数据的处理。

简略版：方法一：枚举分开的位置，将圈化为链，因此要做n次。

　　　　方法二：将链重复两次，即做一个2n-1长度的链，其中第i(i<=n)堆石子与i+n堆相同。

　　　　　　　　对整个长链dp后，枚举(1, n), (2, n+1) ... (n, 2n-1)，取最值即可。

题目描述

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

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

输入格式

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式

输出共2行,第1行为最小得分,第2行为最大得分.

输入输出样例

输入 #1

4
4 5 9 4

输出 #1

43
54

由于只有相邻的石子才能被合成为一堆，因此在所有时刻的任意一堆石子（无论被合成了几次）都可以看做相邻几堆石子的和。即，均可以用一个闭区间[l, r]表示。
进行动态规划时，两堆石子的合并可以被看作两个区间的合并，即两个小区间的信息向一个大区间转移。
为处理环形数据，这里采用的方法是将数组arr重复两次，即arr[i+n] = arr[i]（i<=n）。
设sum[i]为数组arr（重复后）的前缀和，dp1[i][j]、dp2[i][j]分别为第i堆至第j堆石子合并的得分最小值、最大值。
状态转移方程：

dp1[i][j] = min{dp1[i][k] + dp1[k+1][j] + sum[j] - sum[i-1]}
dp2[i][j] = max{dp2[i][k] + dp2[k+1][j] + sum[j] - sum[i-1]}
(i <= k <= j-1)

注意初始化dp1[i][i] = INF，dp2[i][i] = 0。

代码实现后时间复杂度为O(8n³)，相对与朴素的拆环方式（枚举断点做n次dp）的时间复杂度O(n⁴)在数据较大时有优势。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 300
using namespace std;
int dp1[MAXN][MAXN], dp2[MAXN][MAXN];
int arr[MAXN], sum[MAXN];
int n, ans_min = INF, ans_max = -1;
void in_put(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        arr[i+n] = arr[i];
    }
}
void dp(){
    for(int len=2; len<=n; len++){
        for(int i=1; i<=2*n; i++){
            int end = i + len - 1;
            dp1[i][end] = INF, dp2[i][end] = -1;
            for(int j=i; j<end; j++){
                dp1[i][end] = min(dp1[i][end], dp1[i][j] + dp1[j+1][end]);
                dp2[i][end] = max(dp2[i][end], dp2[i][j] + dp2[j+1][end]);
            }
            dp1[i][end] += sum[end] - sum[i-1];
            dp2[i][end] += sum[end] - sum[i-1];
        }
    }
    for(int i=1; i<=n; i++){
        if(dp1[i][i+n-1] < ans_min) ans_min = dp1[i][i+n-1];
        if(dp2[i][i+n-1] > ans_max) ans_max = dp2[i][i+n-1];
    }
}
int main(){
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    in_put();
    for(int i=1; i<=n*2; i++){
        sum[i] = sum[i-1] + arr[i];
        dp1[i][i] = 0, dp2[i][i] = 0;
    }
    dp();
    printf("%d
%d", ans_min, ans_max);
    return 0;
}