首先，注意读题，分成两个集合，而不是分成两个连续的块
所以每一个方案，都可以看成是一个二叉树，其中二叉树中的每一个节点都代表着一个集合
那么，k次以内最坏情况下问出答案即代表这个二叉树的深度不会超过k
所以每一种情况的概率就是对应的二叉树的树的带权路径长度，即所有叶子结点的带权路径长度之和
除以概率之和（是一个定值）
那么这题就转化成了
有若干个数，构造出一个二叉树，每一个叶节点代表一个数，该二叉树的深度不能超过k，使得二叉树的带权路径长度最小
首先如何判断无解的情况？ 如果该二叉树是一个满二叉树，叶节点的个数仍然< n，那不就一定无解么
现在考虑如何求出答案
————————————————————————————————————————————————————————————————————————————————
带权路径长度最小 ？ 如果是k = n的情况， 哈夫曼树
那\(k <= n\) ，就不能使用哈夫曼树了
我们发现，一个子树中的叶节点一共代表的是一个p值排序后连续的区间，一定是一种最优解
那么这个时候就可以进行区间DP了
\[ f[d][i][j] = min(f[d - 1][i][k] + f[d - 1][k + 1][j] + sum[j] - sum[i - 1], f[d][i][j])\]
\(f[d][i][j]\)代表的是当前深度为d，考虑i到j这一个区间时的最优值
这里实际上运用了费用提前计算的思想
因为我们具体并不知道每一个点的具体深度是多少，但是我们每一次划分，都会使得i到j的所有点到达根节点的距离增加，总共增加的值即为\(sum(p[x]) (i <= x <= j)\)
——————————————————————————————————————————————————————————————————————————————
但是这个复杂度是\(O(n^4)\)的，并不能过
（实际上如果优化一下常数，即将dp时反复调用的维度放在后面，也就是把\(f[i][j][d]\)变成\(f[d][i][j]\)，在HZOJ上就可以过了）
——————————————————————————————————————————————————————————————————————————————————————————————————————
打表（或者推柿子）可以发现，这个DP转移方程实际上满足二维DP的决策单调性
（这个式子实际上就是石子合并外面加上了一维深度而已）
可以用四边形不等式优化DP转移
复杂度\(O(n^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, q, a[MAXN];
int gcd(int x, int y) {
if (y == 0)
return x;
return gcd(y, x % y);
}
inline void init(void) {
scanf("%lld%lld", &n, &q);
for (register int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
}
int f[MAXN][MAXN][MAXN], sum[MAXN], loc[MAXN][MAXN];
inline void DP_init(void) {
sort(a + 1, a + n + 1);
for (register int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
for (register int i = 1; i <= n; ++i) {
for (register int j = 1; j <= n; ++j) {
if (i == j)
f[i][j][0] = 0;
else
f[i][j][0] = 1e18;
}
}
}
int ans;
inline void DP(void) {
for (register int d = 1; d <= q; ++d) {
for (register int len = 2; len <= n; ++len) {
for (register int i = 1; i <= n; ++i) loc[i][i] = i;
for (register int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
f[i][j][d] = 1e18;
int now, p;
for (register int k = loc[i][j - 1]; k <= loc[i + 1][j]; ++k) {
now = f[i][k][d - 1] + f[k + 1][j][d - 1] + sum[j] - sum[i - 1];
if (f[i][j][d] > now) {
f[i][j][d] = now;
p = k;
}
loc[i][j] = p;
}
}
}
}
}
inline void work(void) {
if (q <= 9 && (1 << q) < n) {
printf("-1");
return;
}
DP_init();
DP();
ans = f[1][n][q];
printf("%lld/%lld", ans / gcd(ans, sum[n]), sum[n] / gcd(ans, sum[n]));
}
signed main() {
freopen("snow.in", "r", stdin);
freopen("snow.out", "w", stdout);
init();
work();
}#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, q, a[MAXN];
int gcd(int x, int y) {
if (y == 0)
return x;
return gcd(y, x % y);
}
inline void init(void) {
scanf("%lld%lld", &n, &q);
for (register int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
}
int f[MAXN][MAXN][MAXN], sum[MAXN];
inline void DP_init(void) {
sort(a + 1, a + n + 1);
for (register int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
for (register int i = 1; i <= n; ++i) {
for (register int j = 1; j <= n; ++j) {
if (i == j)
f[0][i][j] = 0;
else
f[0][i][j] = 1e18;
}
}
}
int ans;
inline void DP(void) {
for (register int d = 1; d <= q; ++d) {
for (register int len = 2; len <= n; ++len) {
for (register int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
f[d][i][j] = 1e18;
for (register int k = i; k < j; ++k)
f[d][i][j] = min(f[d - 1][i][k] + f[d - 1][k + 1][j] + sum[j] - sum[i - 1], f[d][i][j]);
}
}
}
}
inline void work(void) {
if (q <= 9 && (1 << q) < n) {
printf("-1");
return;
}
DP_init();
DP();
ans = f[q][1][n];
printf("%lld/%lld", ans / gcd(ans, sum[n]), sum[n] / gcd(ans, sum[n]));
}
signed main() {
freopen("snow.in", "r", stdin);
freopen("snow.out", "w", stdout);
init();
work();
}原文：https://www.cnblogs.com/FlySakura/p/11845200.html