马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
标题
529. 宝藏
算法标签: 状态压缩 d p dp dp, 位运算, 贪心
思绪
代价便是 长度 × 当前点的深度 长度 \times 当前点的深度 长度×当前点的深度, 求代价的最小值, 直接想法是 f [ i ] [ j ] [ k ] f[j][k] f[j][k]表现整个聚集状态是 i i i, 末了一层状态是 j j j, 由于末了一层状态也要取决于上一层状态, 上一层状态是 k k k的最小代价, 但是时间复杂度会爆炸, 空间也会爆炸, 须要优化
算状态的时间只能和前一层相连, 只能连向上一层的点, 但是我们思量是否可以连到前面全部的点, 由于须要连最短边, 因此着实也是毗连到 i − 1 i - 1 i−1层的点, 也就不须要毗连到上一层的点, 因此我们重新思量状态表现
f [ i ] [ j ] f[j] f[j]选择的点的聚集是 i i i而且树的高度是 j j j的全部方案的最小代价, 按照末了一层的状态举行聚集的分别, 假设末了一层的状态是 k k k, f [ i ] [ j ] = m i n ( f [ i ⊕ k ] [ j − 1 ] ) + w f[j] = min(f[i \oplus k][j - 1]) + w f[j]=min(f[i⊕k][j−1])+w
代码
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;
- int n, m;
- int d[N][N], f[M][N];
- int g[M];
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- cin >> n >> m;
- memset(d, 0x3f, sizeof d);
- for (int i = 0; i < n; ++i) d[i][i] = 0;
- for (int i = 0; i < m; ++i) {
- int u, v, w;
- cin >> u >> v >> w;
- u--, v--;
- d[u][v] = d[v][u] = min(d[u][v], w);
- }
- // 统计状态i能转移到的状态
- for (int i = 0; i < 1 << n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (i >> j & 1) {
- for (int k = 0; k < n; ++k) {
- if (d[j][k] != INF) g[i] |= 1 << k;
- }
- }
- }
- }
- memset(f, 0x3f, sizeof f);
- for (int i = 0; i < n; ++i) f[1 << i][0] = 0;
- for (int i = 1; i < 1 << n; ++i) {
- for (int j = i - 1 & i; j; j = j - 1 & i) {
- if ((g[j] & i) == i) {
- int pre = i ^ j, cost = 0;
- for (int k = 0; k < n; ++k) {
- if (pre >> k & 1) {
- int val = INF;
- for (int l = 0; l < n; ++l) {
- if (j >> l & 1) val = min(val, d[k][l]);
- }
- cost += val;
- }
- }
- for (int k = 1; k < n; ++k) f[i][k] = min(f[i][k], f[j][k - 1] + k * cost);
- }
- }
- }
- int res = INF;
- for (int i = 0; i < n; ++i) res = min(res, f[(1 << n) - 1][i]);
- cout << res << "\n";
- return 0;
- }
|
发表于 2025-10-3 21:36:31