题解 P1880 【石子合并】

· · 题解

基础的区间dp。。石子合并的强行升级版。。思路就是将一圈石子看成一个序列上的石子，序列为[1,2*n]，至于为什么要这么做，画画图看看。。会发现选择长度为1～n的区间后就是一种选法，那么思路出来了：枚举左端点，计算长度为n的区间的最优汁，于是就可以了。

/* 题目描述

在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.

规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

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

输入输出格式

输入格式：

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

输出格式：

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

*/

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    int n;
    int a[300];
    int dp[300][300];
    int vis[300][300];
    int dp2[300][300];
    int vis2[300][300];
    int f(int i,int j){
        if(vis[i][j])return dp[i][j];
        if(i==j)return 0;
        vis[i][j]=1;
        dp[i][j]=0x3f3f3f3f;
        for(int k=i;k<j;k++){
            dp[i][j]=min(dp[i][j],f(i,k)+f(k+1,j)+a[j]-a[i-1]);
        }
        return dp[i][j];
    }
    int f2(int i,int j){
        if(vis2[i][j])return dp2[i][j];
        if(i==j)return 0;
        vis2[i][j]=1;
        dp2[i][j]=-0x3f3f3f3f;
        for(int k=i;k<j;k++){
            dp2[i][j]=max(dp2[i][j],f2(i,k)+f2(k+1,j)+a[j]-a[i-1]);
        }
        return dp2[i][j];
    }
    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];
        int ans1=0x3f3f3f3f;
        int ans2=-0x3f3f3f3f;
        for(int i=1;i+n-1<=2*n;i++)ans1=min(ans1,f(i,i+n-1)),ans2=max(ans2,f2(i,i+n-1));
        cout<<ans1<<endl<<ans2;
    }