石子合并2（环形求最优解 区间dp）

题目描述

在一个圆形操场的四周摆放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
代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<cmath>

#define Inf 0x3f3f3f3f

const int maxn=1e5+;

typedef long long ll;

using namespace std;

int a[],g[][],sum[];

int dp[][];

int dp2[][];

int main()

{

   int n;

   cin>>n;

   for(int t=;t<=n;t++)

   {

       scanf("%d",&a[t]);

       a[n+t]=a[t];

   }

   for(int t=;t<=*n;t++)

   {

       sum[t]=sum[t-]+a[t];

   }

   memset(dp,Inf,sizeof(dp));

   memset(dp2,,sizeof(dp2));

   for(int t=;t<=*n;t++)

   {

       for(int j=t;j<=*n;j++)

       {

           g[t][j]=sum[j]-sum[t-];

    }

   }

   for(int t=;t<=*n;t++)

   {

       dp[t][t]=;

   }

   for(int l=;l<*n;l++)

   {

       for(int j=;j+l<=*n;j++)

       {

           int r=j+l;

           for(int k=j;k<r;k++)

           {

               dp[j][r]=min(dp[j][r],dp[j][k]+dp[k+][r]+g[j][k]+g[k+][r]);

               dp2[j][r]=max(dp2[j][r],dp2[j][k]+dp2[k+][r]+g[j][k]+g[k+][r]);

        }

    }

   }

   int ans=Inf;

   int ans1=;

   for(int t=;t<=n;t++)

   {

       ans=min(ans,dp[t][t+n-]);

   }

   for(int t=;t<=n;t++)

   {

       ans1=max(ans1,dp2[t][t+n-]);

   }

   cout<<ans<<endl;

   cout<<ans1<<endl;

   return ;

}