精华内容
下载资源
问答
  • 石子合并问题

    万次阅读 多人点赞 2018-07-29 00:09:28
    石子合并问题 石子合并问题是最经典的DP问题。首先它有如下3种题型: (1)有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动任意的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子...

    石子合并问题


    石子合并问题是最经典的DP问题。首先它有如下3种题型:

    (1)有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动任意的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成

    分析:当然这种情况是最简单的情况,合并的是任意两堆,直接贪心即可,每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。

    (2)有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动相邻的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小(或最大)。

    (3)问题(2)的是在石子排列是直线情况下的解法,如果把石子改为环形排列,又怎么做呢?

    (一)任意合并


    题目


    (1)有N堆石子,现要将石子有序的合并成一堆,规定如下:每次只能移动任意的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成

    分析


    当然这种情况是最简单的情况,合并的是任意两堆,直接贪心即可,每次选择最小的两堆合并。本问题实际上就是哈夫曼的变形。

    代码

    STL堆算法

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std; 
    int main()
    {
    	int t;
    	cin>>t;
    	
    	while(t--){
    		int n;
    		cin>>n;
    		vector<int> v;
    		while(n--){
    			int x;
    			cin>>x;
    			v.push_back(x);
    		}
    		long long sum=0;
    		make_heap(v.begin(),v.end(),greater<int>());
    		while(v.size()>1)
    		{
    			int min1=v.front();
    			pop_heap(v.begin(),v.end(),greater<int>());
    			v.pop_back();
    			
    			int min2=v.front();
    			pop_heap(v.begin(),v.end(),greater<int>());
    			v.pop_back();
    			
    			//cout<<min1<<" "<<min2<<endl;
    			sum+=(min1+min2);
    			v.push_back(min1+min2);
    			push_heap(v.begin(),v.end(),greater<int>());
    		}
    		cout<<sum<<endl;
    	}
    	return 0;
    }

    STL优先队列 

    #include<iostream>
    #include<queue>
    //#include<bits/stdc++.h>
    using namespace std;
    const int MAX=1e4+5;
    int n; 
    int main()
    {
    	ios::sync_with_stdio(false);
    	int t;
    	cin>>t;
    	while(t--){
    		int n,x;
    	cin>>n;
    	priority_queue<int,vector<int>,greater<int> >q;
    	for(int i=0;i<n;i++)
    	{
    		cin>>x;
    	q.push(x);
    	}
    	long long sum=0;
    	while(q.size()>1)
    	{
    		int min1=q.top();
    		q.pop();
    		int min2=q.top();
    		q.pop();
    		sum+=(min1+min2);
    		q.push(min1+min2);
    	}
    	cout<<sum<<endl;
    	} 
    	return 0;
     } 
     

    (二)相邻合并


    题目


    有N堆石子,现要将石子有序的合并成一堆,规定如下:

    1.每次只能移动相邻的2堆石子合并 
    2.合并花费为新合成的一堆石子的数量。

    求将这N堆石子合并成一堆的总花费最小(或最大)。

    分析


    我们熟悉矩阵连乘,知道矩阵连乘也是每次合并相邻的两个矩阵,那么石子合并可以用矩阵连乘的方式来解决。

    设dp[i][j]表示第i到第j堆石子合并的最优值,sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式: 
    这里写图片描述

    代码

    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    //#define inf 1<<20
    const int maxn=210;
    int n,a[maxn]; 
    int  dp[maxn][maxn];//dp[i][j]表示从第i堆到第j堆合并的代价
    int  sum[maxn][maxn];//表示石头的数量 
    int main()
    {
    	ios::sync_with_stdio(0);
    	while(cin>>n)
    	{
    		for(int i=1;i<=n;i++)
    		cin>>a[i];
    		memset(sum,0,sizeof(sum));
    		//fill(dp[0],dp[0]+n*n,inf);//错误 
    		fill(dp[0],dp[0]+maxn*maxn,inf);//fill填充量必须是常数 
    
    		for(int i=1;i<=n;i++)
    		sum[i][i]=a[i],dp[i][i]=0;
    		
    		for(int len=1;len<n;len++){//区间长度 
    			for(int i=1;i<=n&&i+len<=n;i++){//区间起点 
    				int j=i+len;//区间终点
    				for(int k=i;k<=j;k++)//用k来表示分割区间 
    				{
    					sum[i][j]=sum[i][k]+sum[k+1][j];
    					dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
    				 } 
    			}
    		}
    		cout<<dp[1][n]<<endl;
    	}
    	return 0;
    } 
    

    (三)环形合并


    题目


    在一个圆形操场的四周摆放着n堆石子(n<= 100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

    编一程序,读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n-1次合并,得分的总和最小;

    比如有4堆石子:4 4 5 9 则最佳合并方案如下:

    4 4 5 9 score: 0
    8 5 9 score: 8
    13 9 score: 8 + 13 = 21
    22 score: 8 + 13 + 22 = 43
    • 1
    • 2
    • 3
    • 4

    输入:

    可能有多组测试数据。 当输入n=0时结束! 第一行为石子堆数n(1<=n<=100);第二行为n堆的石子每堆的石子数,每两个数之间用一个空格分隔。

    输出:

    合并的最小得分,每个结果一行。

    输入样例:

    4 4 4 5 9 
    6 3 4 6 5 4 2 
    0

    输出样例:

    43 
    61

    分析

    假设石头为a1,a2,a3.....an,首尾相连之后就是 a1,a2,a3.....an,a1,a2,a3....an;序列长度变为原来的2倍

    这里写图片描述 
    这里写图片描述 
     

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=450;//区间长度为2*n
    int dp[maxn][maxn];
    int sum[maxn];//前缀和数组
    int a[maxn];//每堆石子的个数
    int main()
    {
        int n,x;
        sum[0]=0;
        while(scanf("%d",&n)!=EOF){
            memset(dp,0,sizeof(dp));
            memset(sum,0,sizeof(sum));
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
                sum[i]=sum[i-1]+a[i];//预处理
                dp[i][i]=0;
            }
    
            int in=1;//首尾相连之后
            for(int i=n+1;i<=2*n;i++)
                sum[i]+=(sum[i-1]+a[in++]);
     
            for(int len=2;len<=n;len++)//枚举区间长度
            {
                for(int i=1;i<=2*n;i++)//枚举区间起点
                {
                    int j=i+len-1;//区间终点
                    if(j>n*2) break;//越界结束
                    for(int k=i;k<j;k++)//枚举分割点,构造状态转移方程
                    {
                        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(sum[j]-sum[i-1]));
                    }
                }
            }
            int MAX=-1;
            for(int i=1;i<=n;i++)//枚举环状序列的起点,长度为n
            MAX=max(dp[i][i+n-1],MAX);//求最大值
            printf("%d\n",MAX);
        }
        return 0;
    }

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,002
精华内容 400
关键字:

石子合并问题