devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

合并石子问题研究与实现_石子合并 c++

作者：繁依Fanyi0 | 2024-04-29 21:46:55

赞

踩

石子合并 c++

一、简单情况

（1）问题描述

  有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。

例题：

      Description

     佳佳的爷爷有一个苹果园，最近苹果都熟了，都从树上掉了下来，佳佳要帮爷爷把树下的苹果堆到一起，他每次可以任意选两堆合成一堆，耗费的体力是这两堆苹果苹果数量的和。他最后的目标是将所有的果子堆成一个大堆，那么他最少耗费的体力是多少呢？

      Input

     多组测试数据，每组数据输入的第一行是一个数n，表示果子原来有多少堆，接下来n个数，每个数表示每堆苹果的个数。

      Output

      对于每组数据，输出一个整数，表明佳佳最少需要的体力。

      Sample Input

      3
      1 1 1

      Sample Output

     5

（2）分析

由于每次可以选择任意的两堆，所以可以选择贪心算法，一种简单的思路是使用sort方法排序之后每次取数组的前两位相加，合并后的新堆需要按大小放到后面剩余的位置上即可。代码如下：

  1. #include <iostream>
  2. #include <algorithm>
  3. #define N 300
  4. using namespace std;
  5. const int INF=1<<10;
  6. int main(){
  7. 	int n,i,j,k;
  8. 	while(cin>>n){
  9. 		int resmin=0;
  10. 		int a[n];
  11. 		for(i=0;i<n;i++){
  12. 			cin>>a[i];
  13. 		}
  14. 		sort(a,a+n);
  15. 		for(i=0;i+1<n;i++){
  16. 			resmin+=a[i]+a[i+1];
  17. 			a[i+1]=a[i]+a[i+1];
  18. 			k=i+1;
  19. 			for(j=i+2;j<n;j++){
  20. 				if(a[k]>a[j]){
  21. 					int temp=a[j];
  22. 					a[j]=a[k];
  23. 					a[k]=temp;
  24. 					k=j;
  25. 				}
  26. 			}
  27. 		}
  28. 			
  29. 	cout<<resmin<<endl;
  30. 	}
  31. 	return 0;
  32. 	
  33. }

但是在OJ上会TimeLimitExceeded，算法本身结果没问题，但是超时了。那么可以换一种思路，该数组的性质符合stl的queue中的优先队列，直接用优先队列构造这组数据即可更高效的实现，代码如下：

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int main()
  5. {
  6.     int n;
  7.     while (cin>>n)
  8.     {
  9.           priority_queue<int,vector<int>,greater<int> > que;   //greater< >指定是小顶堆 ，即从小到大排列 
  10.           int i, crt, cur, a, m, resmin = 0;
  11.           for (i = 0; i < n; ++i)
  12.           {
  13.               scanf("%d", &a);
  14.               que.push(a);
  15.           }
  16.           while (que.size() > 1)
  17.           {
  18.                 crt = que.top();
  19.                 que.pop();
  20.                 cur = que.top();
  21.                 que.pop();
  22.                 m =cur + crt;
  23.                 resmin += cur + crt;
  24.                 que.push(m);
  25.           }
  26.           cout<<resmin<<endl;
  27.     }
  28.     system("pause");
  29.     return 0;
  30. }

以上代码可以AC。到此最简单的情况基本解决了，下面讨论复杂一些的情况。

二、线型情况

（1）问题描述

      在一个操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。

Input

      输入第一行为n(n<1000)，表示有n堆石子，第二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量（<=1000）

Output

      输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。

 Sample Input

      3

      1 2 3

 Sample Output

      9 11

（2）分析

      每次只能选择相邻的两堆合并，所以继续使用贪心算法会有问题，原理是局部最优与全局最优并不是完全一致的。考虑使用动态规划的方法。动态规划需要建立状态转移方程，首先考虑最后一步时的状态，即将两大堆合为一堆，那么只要保证这两堆已为最优解即可。此时有两种思路：

思路一：建立二维素组dp[ ][ ]，dp[i][j]代表从第i个石堆合并到第j个石堆的最优解，0<=i<=j<n；建立数组sum[ ],sum[i]代表从第0个石堆加到第i个石堆的总和，因为要合并一个区间的石堆，无论顺序如何最终一次合并的得分都为所有石堆的总和；

状态转移方程：以求最小得分为例:

即将i~j堆石头的最优解分解为i~k段加上k+1~j段最优解的和加上最后将这两段合并的代价temp：

c++实现代码：

  1. #include <iostream>
  2. using namespace std;
  3. const int INF = 1 << 30;
  4. #define N  1000
  5.  
  6. int dpmin[N][N],dpmax[N][N];
  7. int sum[N];
  8. int a[N],resmin,resmax;
  9.  
  10.  
  11. int main()
  12. {
  13.     int n;
  14.     while(cin>>n)
  15.     {
  16.         for(int i=0;i<n;i++)
  17.             cin>>a[i];
  18.         sum[0] = a[0];
  19.         for(int i=1;i<n;i++)
  20.             sum[i] = sum[i-1] + a[i];
  21.         
  22.     for(int i=0;i<n;i++)
  23.         dpmin[i][i] =dpmax[i][i] =0; //根据从i堆到i堆相当于不合并，所以为0 
  24.     for(int v=1;v<n;v++) //步长从1到n-1
  25.     {
  26.         for(int i=0;i<n-v;i++)  //从第0堆石头开始循环，i<n-v因为是线型的不能i+步长v不能超出n-1    
  27.         {
  28.             int j = i + v;     //求i~j的最优解 
  29.             dpmin[i][j] = INF;//置i!=j的位置为一较大值 
  30.             dpmax[i][j]=0;    //置i!=j的位置为一较小值0 
  31.             int tmp = sum[j] - (i > 0 ? sum[i-1]:0);
  32.             for(int k=i;k<j;k++){
  33.             	dpmin[i][j] = min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j] + tmp);
  34.                 dpmax[i][j] = max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j] + tmp);
  35. 			}
  36.  
  37.         }
  38.     }
  39. 	resmin=dpmin[0][n-1];
  40. 	resmax=dpmax[0][n-1];
  41. 	cout<<resmin<<endl<<resmax<<endl;
  42. 	
  43.     }
  44.     return 0;
  45. }

思路二：建立二维素组dp[ ][ ]，dp[i][j]代表从第i个石堆开始合并j个石堆（总共j+1个石堆）的最优解，0<=i<n-j，1<=j<n；建立数组sum[ ]含义与上面相同；

状态转移方程：以求最小得分为例,

即将从i堆开始的j堆石头的合并分解为从i堆开始的k堆的最优解加上从i+k+1堆开始的j-k-1堆石头的最优解再加上将这两段合并的代价temp：

c++实现代码：

  1. #include <iostream>
  2. using namespace std;
  3. const int INF=1<<10;
  4. #define N 200
  5. int a[N],sum[N];
  6. int dpmax[N][N],dpmin[N][N];
  7. int resmin,resmax;
  8. int main(){
  9. 	int n,i,j,k,t;
  10. 	while(cin>>n){
  11. 		for(i=0;i<n;i++){
  12. 			cin>>a[i];
  13. 		}
  14. 	sum[0]=a[0];
  15. 	for(i=1;i<n;i++){
  16. 		sum[i]=sum[i-1]+a[i];
  17. 	}
  18. 	
  19. 	for(i=0;i<n;i++){  //置从i开始的0推石头为0 
  20. 		dpmax[i][0]=0;
  21. 		dpmin[i][0]=0;
  22. 	}
  23. 	for(j=1;j<n;j++){ //从某一位置开始的1堆循环到某一位置开始的n-1堆 
  24. 		for(i=0;i<n-j;i++){ //从第0堆石头开始循环，i<n-v因为是线型的不能i+步长v不能超出n-1    
  25. 			dpmin[i][j] = INF;//置j!=0的位置为一较大值 
  26.             dpmax[i][j] = 0;  //置j!=0的位置为一较小值0 
  27.             for(k=0;k<j;k++){
  28.             	int temp=sum[i+j]-(i>0? sum[i-1]:0);
  29.             	dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[i+k+1][j-k-1]+temp);
  30.             	dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[i+k+1][j-k-1]+temp);
  31. 			}
  32. 		}
  33. 	}
  34. 	resmin=dpmin[0][n-1];
  35. 	resmax=dpmax[0][n-1];
  36. 	
  37. 	
  38. 	cout<<resmin<<endl<<resmax<<endl;
  39. 	}
  40. 	return 0;
  41. 	
  42. }

三、环型情况

（1）问题描述

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

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

    Input

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

    Output

输出共2行,第1行为最小得分,第2行为最大得分。

Sample Input

   4
4 4 5 9

Sample Output

43
     54

（2）分析

此种情况与第二种情况大体相同，区别是石子是环形摆放的，那么在状态方程迭代时要进行一些对n取模处理。

思路一：  思路与情况二大体一致，不再赘述。相当于对n排石子求了最优解，第一排0~n-1堆，第二排1~n-1加上0~1，第三排2~n-1加上0~2，···
 

c++代码：

  1. #include <iostream>
  2. #include <string.h>
  3. #include <stdio.h>
  4.  
  5. using namespace std;
  6. const int INF = 1 << 30;
  7. const int N = 200;
  8.  
  9. int dpmin[N][N];
  10. int dpmax[N][N];
  11. int sum[N],a[N];
  12. int resmin,resmax;
  13. int n,i,j,k,v;
  14.  
  15. int getsum_ring(int i,int j)  //因为是环形使求temp变得复杂，需要对区间i和j进行判断
  16. {
  17.     if(j < i) return getsum_ring(i,n-1) + getsum_ring(0,j);//如果j<i,那么相当于j超出了n-1到了环的小端,相当于(sum[n-1]-sump[i-1])+(sum[j]-0) 
  18.     else return sum[j] - (i>0 ? sum[i-1]:0);
  19. }
  20.  
  21. void dp(int a[],int n)
  22. {
  23.     for(i=0;i<n;i++)
  24.         dpmin[i][i] = dpmax[i][i] = 0;//根据从i堆到i堆相当于不合并，所以为0 
  25.     for(v=1;v<n;v++) //步长从1到n-1
  26.     {
  27.         for(i=0;i<n;i++)
  28.         {
  29.         	j=(i+v)%n;  //因为是一个环，所以i+v可以超过n-1，进行对n取模操作，n等价于0，n+1等价于1 
  30.             dpmin[i][j] = INF;//置i!=j的位置为一较大值 
  31.             dpmax[i][j] = 0;  //置i!=j的位置为一较小值0 
  32. 			for(k=0;k<v;k++){
  33. 				dpmin[i][j] = min(dpmin[i][j],dpmin[i][(i+k)%n] + dpmin[(i+k+1)%n][j] + getsum_ring(i,j)); //i+k,i+k+1都有可能超过1，所以都对n取模 
  34.                 dpmax[i][j] = max(dpmax[i][j],dpmax[i][(i+k)%n] + dpmax[(i+k+1)%n][j] + getsum_ring(i,j));
  35. 			}
  36.         }
  37.     }
  38.     resmin = dpmin[0][n-1];
  39.     resmax = dpmax[0][n-1];
  40.     for(i=0;i<n;i++)   //相当于对n排石子求了最优解，第一排0~n-1堆，第二排1~n-1加上0~1，第三排2~n-1加上0~2，···现在在这n种情况中再找出最优解 
  41.     {
  42.         resmin = min(resmin,dpmin[i][(i+n-1)%n]);
  43.         resmax = max(resmax,dpmax[i][(i+n-1)%n]);
  44.     }
  45. }
  46.  
  47. int main()
  48. {
  49.     while(cin>>n)
  50.     {
  51.         for(i=0;i<n;i++)
  52.         	cin>>a[i];
  53.         sum[0] = a[0];
  54.         for(i=1;i<n;i++)
  55.             sum[i] = sum[i-1] + a[i];
  56.         dp(a,n);
  57.         cout<<resmin<<endl;
  58.         cout<<resmax<<endl;
  59.     }
  60.     return 0;
  61. }

思路二： 思路与情况二大体一致，不再赘述。一些细节问题需要重新处理，例如temp的计算

c++代码：

  1. #include <iostream>
  2. using namespace std;
  3. const int INF = 1 << 30;
  4. const int N = 200;
  5.  
  6. int dpmin[N][N];
  7. int dpmax[N][N];
  8. int sum[N],a[N];
  9. int resmin,resmax;
  10. int n;
  11.  
  12. int getsum_ring(int i,int j) //因为是环形使求temp变得复杂，需要对区间i和j进行判断
  13. {
  14.     if(i+j >= n) return getsum_ring(i,n-i-1) + getsum_ring(0,(i+j)%n);//如果i+j>=n ,那么此时temp应为i堆之后的n-i-1堆（等价于sum[n-1]-sum[i-1]）之和加上0~（i+j）%n堆之和 
  15.     else return sum[i+j] - (i>0 ? sum[i-1]:0);
  16. }
  17.  
  18. void dp(int a[],int n)
  19. {
  20.     for(int i=0;i<n;i++)    //置从i开始的0推石头为0 
  21.         dpmin[i][0] = dpmax[i][0] = 0;
  22.     for(int j=1;j<n;j++)  //从某一位置开始的1堆循环到某一位置开始的n-1堆 
  23.     {
  24.         for(int i=0;i<n;i++) //从第0堆石头开始循环，i<n因为是环形的可以超出n-1    
  25.         {
  26.             dpmin[i][j] = INF;//置j!=0的位置为一较大值 
  27.             dpmax[i][j] = 0;  //置j!=0的位置为一较小值0 
  28.             for(int k=0;k<j;k++)
  29.             {
  30.                 dpmin[i][j] = min(dpmin[i][j],dpmin[i][k] + dpmin[(i+k+1)%n][j-k-1] + getsum_ring(i,j)); // dpmin[i][k]中的k代表从i堆开始的k堆，不代表堆得序号所以不用对N取模，
  31.                 dpmax[i][j] = max(dpmax[i][j],dpmax[i][k] + dpmax[(i+k+1)%n][j-k-1] + getsum_ring(i,j));//dpmin[(i+k+1)%n][j-k-1]中的（i+k+1）代表堆序号且可能超过n-1所以需要取模 
  32.             }
  33.         }
  34.     }
  35.     resmin = dpmin[0][n-1];
  36.     resmax = dpmax[0][n-1];
  37.     for(int i=0;i<n;i++)  //相当于对n排石子求了最优解，第一排0~n-1堆，第二排1~n-1加上0~1，第三排2~n-1加上0~2，···现在在这n种情况中再找出最优解 
  38.     {
  39.         resmin = min(resmin,dpmin[i][n-1]);
  40.         resmax = max(resmax,dpmax[i][n-1]);
  41.     }
  42. }
  43.  
  44. int main()
  45. {
  46.     while(cin>>n)
  47.     {
  48.         for(int i=0;i<n;i++)
  49.         	cin>>a[i];
  50.         sum[0] = a[0];
  51.         for(int i=1;i<n;i++)
  52.             sum[i] = sum[i-1] + a[i];
  53.         dp(a,n);
  54.         cout<<resmin<<endl;
  55.         cout<<resmax<<endl;
  56.     }
  57.     return 0;
  58. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/509976
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号