洛谷P1880 石子合并（区间DP）（环形DP）

To 洛谷.1880 石子合并

题目描述

在一个园形操场的四周摆放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

代码：

先拆环为链，再做区间DP。

 #include<cstdio>

 #include<iostream>

 #define maxn 206

 using namespace std;

 int n,sum[maxn];

 int dpmin[maxn][maxn],dpmax[maxn][maxn];

 int main()

 {

     scanf("%d",&n);

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

     {

         scanf("%d",&a);

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

         sum[i+n]=sum[i];

     }

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

       sum[i+n]+=sum[n];

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

       for(int i=;i<=n*--len;i++)

       {

             int j=i+len;

             int res1=0x7fffffff;

             int res2=-;

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

             {

               res1=min(res1,dpmin[i][k]+dpmin[k+][j]+sum[j]-sum[i-]);

                 res2=max(res2,dpmax[i][k]+dpmax[k+][j]+sum[j]-sum[i-]);

           }

             dpmin[i][j]=res1;

             dpmax[i][j]=res2;

       }

     int MIN=0x7fffffff,MAX=;

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

        MIN=min(dpmin[i][i+n-],MIN),MAX=max(dpmax[i][i+n-],MAX);//!dp[i][i+n-1]

     printf("%d\n%d",MIN,MAX);

     return ;

 }

洛谷P1880 石子合并（区间DP）（环形DP）的相关教程结束。