显然,这题和哈夫曼编码有着难以割舍的关系.
我们在基础课的时候学习过,当区间不能随意移动的时候,要使用区间dp,当区间可以移动的时候,要使用哈夫曼树
然而这题怎么看怎么像哈夫曼编码,但题意中有一个很重要的题眼,保证字典序
翻译一下就是,排在前面的元素的编码一定要比排在后面的元素的编码小,这就联想到我们的哈夫曼编码,但他并不能保证字典序
那就只能在保证区间前后顺序不变的情况下,去做哈夫曼编码,然后就可以发现,这种情况下的哈夫曼编码可以简化成区间dp
所以就挖掘出来了本题的真正模型,就是区间dp,石子合并
这里放一下原题(一模一样,两个题的代码可以互相交,都能AC) Acwing 284.石子合并
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int f[N][N];
int w[N],s[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 1; i <= n; i ++ ) s[i]=s[i-1]+w[i];
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[i][j]=0x3f3f3f3f;
for(int k=i;k<=j-1;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
}
}
}
cout<<f[1][n];
return 0;
}