算法设计与分析——动态规划——石子合并问题

叁歲伎倆 2022-10-14 15:56 219阅读 0赞

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

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    #define Ma_x 99999
    #define Mi_x 0 
    #define min(a,b) a<b?a:b
    #define max(a,b) a>b?a:b 
    
    int n,w[200],dp[200][200],dq[200][200];
    //n表示堆数，w表示每队的数量，dp[i][j]表示从第i堆开始合并j堆（包括第i堆）后的最小花费 ,dq表示最大 
    
    int sum(int i,int t){
        //从第i堆开始,t个石堆合，最后一次的合并的花费 
        int k,s=0,k1;
        for(k=i;k<i+t;k++){
        
            k1=k%n;
            if(k1==0) k1=n;
            s=s+w[k1];   
        }
        return s;
    }
    
    void stone_problem()
    {
        
    	  for(int t=2;t<=n;t++){
        
            for(int i=1;i<=n;i++){
        
                dp[i][t]=Ma_x;
                dq[i][t]=Mi_x; 
                for(int k=1;k<t;k++){
        
                    dp[i][t]=min(dp[i][t],dp[i][k]+dp[(i+k-1)%n+1][t-k]+sum(i,t));
                    dq[i][t]=max(dq[i][t],dq[i][k]+dq[(i+k-1)%n+1][t-k]+sum(i,t));
    			}
            }
        }
        int mini=Ma_x;
    	int maxi=Mi_x; 
        for(int i=1;i<=n;i++){
        //从第几堆石子开始结果最小 
            mini=min(mini,dp[i][n]);  
    		maxi=max(maxi,dq[i][n]); 
        }
        cout<<"输出合并成一堆的最小花费为："<<mini<<endl;
    	cout<<"输出合并成一堆的最小花费为："<<maxi<<endl;
       
    }
    int main(){
        
        cout<<"输入石子的堆数";
    	cin>>n;
    	
        for(int i=1;i<=n;i++){
        
           cin>>w[i];
            dp[i][1]=0;//表示合并一堆的花费，没有合并则花费为0 
            dq[i][1]=0; 
    	}
       
     	 stone_problem();
    }

![在这里插入图片描述][20210522142707464.png]

[20210522142707464.png]: /images/20221014/248092acaf8049aa94e2c8aee8fece6f.png