题目描述

合并果子

每合并的一个过程对应一棵完全二叉树（根节点是0）

将数字存入树中时是按照根节点最大，依次减小的顺序

最后的代价等于两边子树的代价之和，而每个叶节点x在合并过程中被计算的次数=其与根节点的距离

dp:找到整个集合的最优解（分别求出每一类的最优解，再整合）
贪心：也是找到整个集合的最优解（证明最优解一定在某一个子集里，则其他的子集可以丢掉）

第一类：合并最小两堆
第二类：其他的所有方案

若证明第一类中一定有最优解，则之后便可以按照这种方案递归做

（1）两个最小的点在同一层，但是不是同一个根节点的子节点，则可以与该子结点在同一个根节点下的另一个子节点交换，则最后总代价不变（因为还是在同一层）
（2）两个最小的点不在同一层，将两个点交换，则总代价会变化，（因为到根节点的距离变化了）变小
综上，合并最小的两堆（第一类）的代价一定小于等于其他方案，所以最优解一定在第一类中

一共有n个元素，每个元素的操作的时间复杂度为O(logn)，所以总共的时间复杂度为O(nlogn)

算法1

DP（内存超限）

C++ 代码

#include<iostream>
using namespace std;
const int N=10010;
int n;
int f[N][N];
int s[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            f[i][j]=1e8;
            for(int k=i;k<j;k++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

算法2

贪心

定义优先队列：在优先队列中，优先级高的元素先出队列。
使用元素类型的<操作符来确定它们之间的优先级关系。
<操作符可知在整数中元素大的优先级高（从大到小输出）

<操作符与>无直接联系

将元素从小到大输出：
priority_queue < int , vector < int > , greater < int > > qi2;第二个参数为容器类型，第三个参数为比较函数

C++ 代码

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int>> heap;  //定义优先队列
    while(n--)
    {
        int x;
        cin>>x;       //读入果子数量
        heap.push(x);   //将果子插入到堆中

    } 
    int res=0;   //答案
    while(heap.size()>1)   //当当前果子的堆数大于1时
    {
        int x=heap.top();   //先取出最小的一堆
        heap.pop();    //将这堆删掉
        int y=heap.top();    //再取出最小的一堆
        heap.pop();      //将这堆删掉
        res+=x+y;
        heap.push(x+y);
    }
    cout<<res<<endl;
    return 0;
}