hdu 5290 Bombing plan（树形dp）

分类：

题目链接：hdu 5290 Bombing plan

dpDestroy[u][i]表示以u为根节点的子树全部被摧毁，并且向上还可以破坏到距离u为i的城市；dpSafe[u][i]表示以u为根节点的子树中有距离u深度为i的城市还未被破坏。

dpDestroy[u][i] = dpDestroy[v][i+1] + sum{ min(dpDestroy[k][j], dpSafe[k][j])（j≤i）| k为除了v以外的子节点}

dpSafe[u][i] = dpSafe[v][i-1] + sum{ min(dpSafe[k][j], dpDestroy[k][j]) （j≤i）| k为除了v以外的子节点}

然后在转移一下u节点放炸弹的情况，，这样的直接做的复杂度是o（n * w * w）

对于每个节点，可以维护一个前缀最小值，加速查询，minDestroy[u][i] = min{ dpDestroy[u][j] （j≤i）}

#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int maxn = 1e5 + 5;const int maxm = 100;const int inf = 0x3f3f3f3f;int N, W[maxn], dpDestroy[maxn][maxm + 5], dpSafe[maxn][maxm + 5];int minDestroy[maxn][maxm + 5], minSafe[maxn][maxm + 5];vector<int> G[maxn];void init () {for (int i = 1; i <= N; i++) {scanf("%d", &W[i]);G[i].clear();}int u, v;for (int i = 1; i < N; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}}void dfs (int u, int f) {for (int i = 0; i <= maxm; i++)dpDestroy[u][i] = dpSafe[u][i] = N;int tmp = 0;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (v == f)continue;dfs(v, u);tmp += min(minDestroy[v][W[u]], (W[u] ? minSafe[v][W[u]-1] : inf));}dpDestroy[u][W[u]] = tmp + 1;for (int i = 0; i < maxm; i++) {int p = 0, q = 0;for (int j = 0; j < G[u].size(); j++) {int v = G[u][j];if (v == f)continue;p += min(minDestroy[v][i + 1], (i == 0 ? inf : minSafe[v][i-1]));q += min(minDestroy[v][i], (i == 0 ? inf : minSafe[v][i-1]));}for (int j = 0; j < G[u].size(); j++) {int v = G[u][j];if (v == f)continue;//dpDestroy[u][i] = min(dpDestroy[u][i], p+dpDestroy[v][i+1]-min(minDestroy[v][i+1], minSafe[v][i]));if (i) {dpDestroy[u][i] = min(dpDestroy[u][i], p+dpDestroy[v][i+1]-min(minDestroy[v][i+1], minSafe[v][i-1]));dpSafe[u][i] = min(dpSafe[u][i], q + dpSafe[v][i-1] – min(minDestroy[v][i], minSafe[v][i-1]));} else {dpDestroy[u][i] = min(dpDestroy[u][i], p+dpDestroy[v][i+1]-min(minDestroy[v][i+1], inf));dpSafe[u][i] = min(dpSafe[u][i], q);}}}if (G[u].size() == 1)dpSafe[u][0] = 0;minDestroy[u][0] = dpDestroy[u][0];minSafe[u][0] = dpSafe[u][0];for (int i = 1; i <= maxm; i++) {minDestroy[u][i] = min(minDestroy[u][i-1], dpDestroy[u][i]);minSafe[u][i] = min(minSafe[u][i-1], dpSafe[u][i]);}}int main () {while (scanf("%d", &N) == 1) {init();dfs(1, 0);printf("%d\n", minDestroy[1][maxm]);}return 0;}

上一篇hdu 5225 Tom and permutation（回溯）下一篇hdu 5292 Pocket Cube

顶0踩0

一个人，一条路，人在途中，心随景动，

相关文章：

你感兴趣的文章：

标签云：