NK 1137: 石子合并问题

1137: 石子合并问题

Time Limit: 1500 ms Memory Limit: 10000 kB Judge type: Multi-cases Total Submit : 1315 (282 users) Accepted Submit : 300 (202 users) Page View : 10921

Font Style: Aa Aa Aa

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

编程任务：对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。

Input

输入包括多组测试数据，每组测试数据包括两行。

第1 行是正整数n，1<=n<=100，表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。

Output

对于每组输入数据，输出两行。

第1 行中的数是最小得分；第2 行中的数是最大得分。

Sample Input

4
4 4 5 9

Sample Output

43
54

Source

福建省优质硕士课程《算法设计与分析》教学组

Best User : cww


// dp[i][j] 表示区间 i到j的石子合并的最大/最小代价

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define INF 1000000000
int dp_max[210][210],dp_min[210][210];

int main()
{
    int n;
    int a[210];
    int sum[210];
    while(scanf("%d",&n)!=EOF){

      int i,j,k;
      memset(dp_max,0,sizeof(dp_max));
      memset(dp_min,0,sizeof(dp_max));

      for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i+n]=a[i];
      }
      for(i=1;i<=2*n;i++)
        sum[i]=sum[i-1]+a[i];

      for(k=2;k<=n;k++) //枚举区间长度
         for(i=1;i+k-1<=2*n;i++){
           //      printf("%d %d %d==|==",i,i+k-1,j);
          dp_min[i][i+k-1]=INF;
            //    printf("?");
          for(j=i;j<i+k;j++){
        //  printf("%d ",j);
           dp_max[i][i+k-1]=max(dp_max[i][i+k-1],dp_max[i][j]+dp_max[j+1][i+k-1]);
           dp_min[i][i+k-1]=min(dp_min[i][i+k-1],dp_min[i][j]+dp_min[j+1][i+k-1]);
        }

       dp_max[i][i+k-1]+=sum[i+k-1]-sum[i-1];
       dp_min[i][i+k-1]+=sum[i+k-1]-sum[i-1];

      }
      int Max=0,Min=INF;
      for(i=1;i<=n;i++){
         Max=max(Max,dp_max[i][i+n-1]);
         Min=min(Min,dp_min[i][i+n-1]);
      }

      printf("%d
%d
",Min,Max);
    }
    return 0;
}