【四边形不等式】noi95- 合并石子

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

【题目大意】

在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最大得分。

【思路】

设 dp[i][j] 表示第 i 到第 j 堆石子合并的最优值，sum[i][j] 表示第 i 到第 j 堆石子的总数量。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int N=;

 const int INF=0x7fffffff;

 int n;

 int a[N],sum[N],dp[N][N],s[N][N];

 void f()

 {    for (int i=;i<=n;i++) dp[i][i]=,s[i][i]=i;

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

      {

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

         {

             int j=i+r;

             if(j>n) break;

             dp[i][j]=INF;

             for (int k=s[i][j-];k<=s[i+][j];k++)

             {

                 if(dp[i][j]>dp[i][k]+dp[k+][j])

                 {

                     dp[i][j]=dp[i][k]+dp[k+][j];

                     s[i][j]=k;

                 }

             }

             dp[i][j]+=sum[j]-sum[i-];

         }

     }

 }

 int main()

 {

      while(~scanf("%d",&n))

      {

          sum[]=;

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

         {

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

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

         }

         f();

         printf("%d\n",dp[][n]);

      }

      return ;

 }