石子合并问题----贪心，动态规划_石子合并问题贪心算法

第一类直接合并

题目链接

148. 合并果子 - AcWing题库https://www.acwing.com/problem/content/150/

n堆石子，每次合并的花费为两堆石子数目之和，求怎样合并可以使得合并为一整堆石子的总花费最少

实际上这就是Hufffman编码的变形，运用贪心策略，每次找出最小的两堆合并即可。

具体AC代码如下：

//哈夫曼树的经典贪心  
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e4+4;
int main(){
    priority_queue<int,vector<int>,greater<int>> heap;//最小堆
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        heap.push(x);
    }
    int res=0;
    while(heap.size()>1){
        int a=heap.top();
        heap.pop();
        int b=heap.top();
        heap.pop();
        heap.push(a+b);
        res+=a+b;
    }
    cout<<res;
    return 0;
}

第二类相邻合并

题目链接

282. 石子合并 - AcWing题库https://www.acwing.com/problem/content/description/284/每次合并只能合并相邻的两堆石子，局部最优不等于全局最优，所以就是不能使用贪心算法，改考虑DP。

对于这种区间DP问题

有状态转移方程如下：

dp[i][j]  代表的含义为 合并从第i个石子到第j个石子所需的最少的代价。

当i==j时，就是一堆石子，所以dp[i][j]=0

当i≠j 时，考虑从其他状态转移而来，则有以下转移方程：

dp[i][j] = min(dp[i][j],d[i][k]+dp[k+1][j]+sum(i,j)) 

sum(i,j)代表合并i到j这些石子所要耗费的代价。

此外，区间DP还要考虑区间的长度，要枚举每一个区间。因为大区间是从小区间状态转移而来的，所以可以从小区间下手求解。这类问题有模板。

//很像哈夫曼树来着    不是   具有明显的区间性质 不是贪心
//用集合求解可以吗
//贪心的思想可以嘛，就是每次都找和最小的两个集合合并  不可以   局部最优不代表全局最优
#include<iostream>
#include<climits>
#include<cstring>
using namespace std;
int dp[306][306];
const int INF=0x3f3f3f3f;
int main(){
    int n;
    cin>>n;
    int a[305],sum[305];
    memset(dp,INF,sizeof(dp));     //记得初始化
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//求前缀和
       
    }
    //len
    
    for(int len=1;len<=n;len++){//枚举长度
        for(int i=1;i+len-1<=n;i++){//枚举起点
            int j=i+len-1;//计算出终点
                if(len==1) dp[i][j]=0;
                else{
                   // dp[i][j]=1e9;//这句话坚决不能少！！！
                    for(int k=i;k<j;k++){//保证k是严格小于j的，否则k+1就会越界
                        dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
                    }
                }
            }
        
    }
    cout<<dp[1][n];
    return 0;
}

第三类环形合并

题目链接

P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1880第二类下的改编，将线性改为了环。

解决思路就是把环展开，变成一个两倍数组，这样就能遍历到所有石子开头的长度为n的内容。

#include<iostream>
using namespace std;
const int N=205;//这个地方很容易出现段错误，数组越界
int a[N];
int sum[N];
int dp1[N][N];
int dp2[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){//枚举长度
        for(int i=1;i+len-1<=2*n;i++){//枚举起点
            int j=i+len-1;//计算终点
            
            if(len==1) {dp1[i][j]=0;dp2[i][j]=0;}
            else{
                dp1[i][j]=0x3f3f3f3f;//对于求min赋初值
                for(int k=i;k<j;k++){//计算最小值
                    dp1[i][j]=min(dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1],dp1[i][j]);
                    dp2[i][j]=max(dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1],dp2[i][j]);
                }
            }
        }
    }
    int maxl=0,minl=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        maxl=max(maxl,dp2[i][i+n-1]);
        minl=min(minl,dp1[i][i+n-1]);
    }
    cout<<minl<<endl;
    cout<<maxl<<endl;
    return 0;
}