梦熊十三联测 D题 电报
这道题感觉类似诈骗题,可以很轻松的猜到一个假结论,可以试试以下数据
这道题可以使用一棵(类似于哈夫曼树的)二叉树来进行编码。每个非叶子节点的两条子边权值分别为1和2。每个叶子节点对应了一个字符,其代价即为根到该叶子结点的路径长度。
最优解中出现频次越大的字符串深度越小,考虑由浅入深构造整棵二叉树。
可以设f[i] [a] [b] [l] 表示构造二叉树的深度为i,其中深度为i-1的节点有a个,深度为i的节点有b个,深度不超过i-2的叶子有l个。我们可以枚举深度i-1保留k个节点作为叶子,将剩下的节点扩展。由此可以得到O(n^5)的做法
那这样做肯定是会超时的,我们要考虑优化做法
转移时不需要记录深度(将贡献拆分到每一层),可以减少一维做到O(n^4)
进一步将枚举的过程省略,将其拆分为两种转移:扩展一个节点,或者将深度加一。
优化后的时间复杂度为O(n^3)
这道题暴力做法能拿到30pts(果真是暴力出奇迹)
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int lowbit(int x) { return x & (-x); }
int n, a[100010], dp[100010], s[100010], sum[100010];
signed main() {
freopen("telegram.in", "r", stdin);
freopen("telegram.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) s[1 << (i - 1)] = i;
sum[0] = 0;
for (int msk = 1; msk < (1 << n); msk++) sum[msk] = sum[msk ^ lowbit(msk)] + a[s[lowbit(msk)]];
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[1 << (i - 1)] = 0;
for (int msk = 1; msk < (1 << n); msk++) {
for (int c = (msk - 1) & msk; c; c = (c - 1) & msk) {
dp[msk] = min(dp[msk], dp[c] + dp[msk ^ c] + sum[c] + 2 * sum[msk ^ c]);
}
}
cout << dp[(1 << n) - 1];
return 0;
}
AC代码:
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
freopen("telegram.in", "r", stdin);
freopen("telegram.out", "w", stdout);
}
using ll = long long;
const int kL = 405, inf = (1 << 30) - 3;
int n;
array<int, kL> a, pre;
array<array<array<array<int, kL>, kL>, 40>, 2> f;
void chkmn(int& x, int y) { (x > y) && (x = y); }
int main() {
file();
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(All(a, 1, n));
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
for (auto& A : f)
for (auto& B : A)
for (auto& k : B) k.fill(inf);
f[1][1][0][1] = -a[1];
for (int i = 1; i <= n; i++) {
int cr = (i & 1), nx = !(i & 1);
for (int j = 1; j < 38; j++)
for (int k = 0; k <= i; k++) fill(All(f[nx][j][k], 0, i), inf);
for (int j = 1; j < 38; j++)
for (int k = 0; k <= i; k++) {
for (int p = k; p + k <= i; p++) chkmn(f[cr][j + 1][p - k][k], f[cr][j][k][p]);
for (int p = 0; p + k <= i; p++) chkmn(f[nx][j][k][p + 1], f[cr][j][k][p] - j * a[i + 1]);
}
}
ll ans = inf, sum = accumulate(All(a, 1, n), 0ll);
for (int i = 1; i < 38; i++) ans = min(ans, sum * i + f[n & 1][i][0][1]);
cout << ans << "\n";
return 0;
}