题目描述

在一个圆形操场的四周摆放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,f[i][j]表示i到j这一段合并成一堆的最大值，f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + sum[i+1][j]) i<=k<j,对于环形的处理是把这个环复制,接到末尾,其中sum[i+1][j]表示a[i] + a[i+1] + .. + a[j].
AC代码:

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 int n,f1[][],f2[][],num[],maxans,minans = ,he[];//f1为最大值,f2为最小值

 int max(int a,int b) {

     if(a >= b) return a;

     else return b;

 }

 int min(int a,int b) {

     if(a <= b) return a;

     else return b;

 }

 int main()

 {

     cin >> n;

     memset(f2,0x7f7f7f,sizeof(f2));//将最小值初始位足够大

     for(int i = ; i <= n; i++) {//读入

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

         he[i] = he[i-] + num[i];

         f2[i][i] = ;

     }

     for(int i = n+; i <= n+n; i++) {//将这个环复制一遍接到末尾

         num[i] = num[i-n];

         he[i] = he[i-] + num[i];

         f2[i][i] = ;

     }

     for(int p = ; p < n; p++)//枚举区间长度

         for(int i = , j = i + p; i < n + n && j < n + n; i++, j = i + p)//枚举起点和终点

             for(int k = i; k < j; k++){//设置断点

                 f1[i][j] = max(f1[i][j], f1[i][k] + f1[k+][j] + he[j] - he[i-]);//状态转移

                 f2[i][j] = min(f2[i][j], f2[i][k] + f2[k+][j] + he[j] - he[i-]);//状态转移

             }

     for(int i = ; i <= n; i++) {//找最大值和最小值

         maxans = max(maxans,f1[i][i+n-]);

         minans = min(minans,f2[i][i+n-]);

     }

     printf("%d\n%d",minans,maxans);

 return ;

 }

巴特西

洛谷 P1880 [NOI1995]石子合并

题目描述

输入输出格式

输入格式：

输入输出样例

最新文章

热门文章