石子合并（区间dp）

题目描述

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

试设计出一个算法,计算出将 NNN 堆石子合并成 111 堆的最小得分和最大得分。

输入格式

数据的第 111 行是正整数 NNN，表示有 NNN 堆石子。

第 222 行有 NNN 个整数，第 iii 个整数 aia_iai​ 表示第 iii 堆石子的个数。

输出格式

输出共 222 行，第 111 行为最小得分，第 222 行为最大得分。

输入输出样例

输入 #1

4
4 5 9 4

输出 #1

43
54

说明/提示

1≤N≤100，0≤ai≤200

dp[i][j]为从第i个位置到第j个位置的最小（大）结果；可以看成两堆合并；

只有两堆的时候，直接将两堆合并；当大于两堆的时候，最后也是将两个堆合并；

由此：dp【i】【j】=min(dp[i][j],dp[i][mid]+dp[mid+1][j]+sum[j]-su[i-1]);

最大好说，最小的话，右上三角要初始化为 一个较大数，但是对角线要初始化为0；

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[205];
    int sum[205]={0};
    int dp1[205][205],dp2[205][205];
//    memset(dp1,0,sizeof(dp1));
//    memset(dp2,-1,sizeof(dp2));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[n+i]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
        dp1[i][i]=0;
    }
    for(int i=1;i<=2*n;i++){
        for(int j=i;j<2*n;j++){
            if(j==i)dp1[i][j]=0;
            else dp1[i][j]=1000000;
        }
    }
/*        for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            cout<<dp1[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"************"<<endl;    */
    for(int i=2;i<=n;i++){
        for(int l=1,r;l<2*n-i+1;l++){
        //    dp1[l][r]=100000;
        //    dp2[l][r]=-1;
            r=l+i-1;
            for(int mid=l;mid<r;mid++){
                dp1[l][r]=min(dp1[l][r],dp1[l][mid]+dp1[mid+1][r]+sum[r]-sum[l-1]);
                dp2[l][r]=max(dp2[l][r],dp2[l][mid]+dp2[mid+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
/*        for(int i=1;i<=2*n;i++){
        for(int j=1;j<=2*n;j++){
            cout<<dp1[i][j]<<" ";
        }
        cout<<endl;
    }*/
    int ans1=123456789,ans2=-1;
    for(int i=1;i<=n;i++){
        ans1=min(ans1,dp1[i][i+n-1]);
        ans2=max(ans2,dp2[i][i+n-1]);
    }
    cout<<ans1<<endl<<ans2<<endl;
}