题目描述

链接：https://ac.nowcoder.com/acm/problem/50493
来源：牛客网

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

题目思路

原问题：n堆石子合并n-1次后得分总和的最大值/最小值
->从第i堆石子开始向后合并n堆石子得分总和的最大值/最小值
子问题：从第i堆石子开始向后合并j堆石子得分总和的最大值/最小值。
石子环形摆放，在求得分时就要考虑到取模运算。
设dp1[i][j], 从第i堆石子开始向后合并j堆的得分总和最小值；
dp2[i][j], 从第i堆石子开始向后合并j堆的得分总和最大值；
sum[i][j], 从第i堆石子开始向后数j堆的石子数之和。
状态转移方程 dp1[i][j] = min（dp1[i][j], dp1[i][k]+dp1[(i+k-1)%n + 1][j-k]）,
dp2[i][j] = max（dp2[i][j], dp2[i][k]+dp2[(i+k-1)%n + 1][j-k]）

Q1.怎样理解(i+k-1)%n + 1？

(i+k-1)%n 计算上一部分石子最后一堆的位置。取模运算是为了，若上一堆石子已经将圆圈的头尾包含进去，就需要找到当前堆石子的正确序号。不直接（i+k）%n 是为了防止出现dp[0][j-k]的情况。

Q2.对dp1、dp2数组的遍历顺序是怎样的？

根据状态转移方程，可以发现dp数组填充时，dp[i][j]需要用到在其左下方位的数字。因此不能采用从上到下、从左向右的遍历方式。
本题中采用先列后行的遍历方式，就解决了问题。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 210;
long long dp1[MAXN][MAXN], dp2[MAXN][MAXN], sum[MAXN][MAXN];
int a[MAXN];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        ///a[i+n] = a[i];
    }
    for(int i = 1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=i; k<i+j; k++)
            {
                int k1 = k%n;
                if(k1==0) k1 = n;
                sum[i][j] += a[k1]; 
            }
        }
    }
    long long minx = 1000000, maxx = 0;
    for(int j=2;j<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            dp1[i][j] = 1000000;//注意这里预设最小值的操作，用memset能预设的值最大为255了
            dp2[i][j] = 0;
            for(int k=1;k<j;k++)//注意条件是k<j，不是<=, <=会对max造成影响
            {
                dp1[i][j] = min(dp1[i][j], (dp1[i][k] + dp1[(i+k-1)%n+1][j-k] + sum[i][j]));    
                dp2[i][j] = max(dp2[i][j], (dp2[i][k] + dp2[(i+k-1)%n+1][j-k] + sum[i][j]));

            }
        }    
    }

    for(int i=1;i<=n;i++)
    {
        if(dp1[i][n] < minx) minx = dp1[i][n];
        if(dp2[i][n] > maxx) maxx = dp2[i][n];
    }
    printf("%d\n%d\n",minx,maxx);
    return 0;
}