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+][j] + sum[j] - sum[i-]}

dp2[i][j] = max{dp2[i][k] + dp2[k+][j] + sum[j] - sum[i-]}

(i <= k <= j-)

注意初始化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 = -;

void in_put(){

    scanf("%d", &n);

    for(int i=; i<=n; i++){

        scanf("%d", &arr[i]);

        arr[i+n] = arr[i];

    }

}

void dp(){

    for(int len=; len<=n; len++){

        for(int i=; i<=*n; i++){

            int end = i + len - ;

            dp1[i][end] = INF, dp2[i][end] = -;

            for(int j=i; j<end; j++){

                dp1[i][end] = min(dp1[i][end], dp1[i][j] + dp1[j+][end]);

                dp2[i][end] = max(dp2[i][end], dp2[i][j] + dp2[j+][end]);

            }

            dp1[i][end] += sum[end] - sum[i-];

            dp2[i][end] += sum[end] - sum[i-];

        }

    }

    for(int i=; i<=n; i++){

        if(dp1[i][i+n-] < ans_min) ans_min = dp1[i][i+n-];

        if(dp2[i][i+n-] > ans_max) ans_max = dp2[i][i+n-];

    }

}

int main(){

//    freopen(".in", "r", stdin);

//    freopen(".out", "w", stdout);

    in_put();

    for(int i=; i<=n*; i++){

        sum[i] = sum[i-] + arr[i];

        dp1[i][i] = , dp2[i][i] = ;

    }

    dp();

    printf("%d\n%d", ans_min, ans_max);

    return ;

}

巴特西

NOI1995 石子合并 [Luogu P1880]

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章