P1880 [NOI1995] 石子合并

· · 题解

这里就不详细解释了，代码里有详细的注释
题目传送门 

//石子合并是道有环的动态规划题，而对于环来说，最简单有效的方式就是暴力断环，但这样的话4层循环n^4时间复杂度，很明显会超时，所以我们把数组开大两倍，当做把环里面所有的可能都拆出来，去枚举，n^3复杂度，不会超时 
//f[i][j]表示从i到j所花费的体力最小值 ，dp[i][j]表示从i到j所花费的体力最大值 
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100 * 2 + 5;//数组开两倍，用来存环带来的特殊情况 

int a[N],n,s[N],f[N][N],dp[N][N];//s用来存前缀和，f数组用来存最小值，dp数组用来存最大值 

int main(){

    memset (f,0x3f3f3f3f,sizeof(f));//记得初始化，不然最小值是0 

    cin >> n;

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

        cin >> a[i];
        s[i] = s[i - 1] + a[i];//前缀和基本公式 
    }
    for (int i = n + 1;i <= n * 2;i ++){//初始化一下后面的n 

        a[i] = a[i - n];
        s[i] = s[i - 1] + a[i];//也要有前缀和 
    }

    for (int i = 1;i <= n * 2;i ++){//注意要小于等于n*2，因为这两倍空间都需要初始化 

        f[i][i] = 0;//表示现在这堆石子不移动，所以不需要消耗体力 
        dp[i][i] = 0;

    }

    for (int len = 2;len <= n;len ++){//这层循环枚举区间长度 
        for (int l = 1;l <= n * 2 - len + 1;l ++){//这层枚举左端点，n*2-len+1是最后一个左端点的位置，如果超过，就越界了 

            int r = l + len - 1;//知道了长度和左端点，右端点也就知道啦 

            for (int k = l;k < r;k ++){//在区间中找出一个k,使得左端点到k的所花费的体力加右端点到k所花费的体力最小 

                f[l][r] = min (f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);//找最小的，注意要加前缀和，因为最后剩下的两堆石子还要合并 
                dp[l][r] = max (dp[l][r],dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);

            }

        }
    }
    int minn = 0x3f3f3f3f,maxx = 0;//附个初值，好取大小 
    for (int i = 1;i <= n;i ++){

        minn = min (minn,f[i][i + n - 1]);//表示从i开始，长度为n的区间中所耗费体力最小的那个 
        maxx = max (maxx,dp[i][i + n - 1]);//表示从i开始，长度为n的区间中所耗费体力最大的那个  

    }
    cout << minn << '\n' << maxx;//最后输出答案 
    return 0;//华丽结束 
}