前言：
没有，下一个
学习博客：
简单介绍：
题目
Fire
给定一棵树，对于任意节点 \(i\) 需要满足至少一个条件。
1.可以花费一定代价 \(w_i\) 建消防站；
2.离它最近的消防站的之间的距离不超过 \(D_i\)，
求满足条件的最小花费。
\(dp_{i, j}\): 表示城市 \(i\) 的负责点是 \(j\) 的情况。
再来一个数组 \(g_i\) 表示 \(i\) 的子树内负责点不定的最小代价
\(dp_{i, j}\) 向上传递，由儿子传递到父亲。
对于一棵树来说，父亲为 \(x\), 儿子为 \(y\)。
- 如果 \(x\), \(y\) 由同一个节点 \(a\) 负责,
\(dp_{x, a} += dp_{y,a} - w_a\);
直接减去重复计算的 \(w_a\) 即可
- 如果x, y 不由同一个节点负责，那就不用管 y 具体由哪个节点负责，直接用 \(g_y\) 转移
\(dp_{x,a} += g_y\)
关于 \(g_x\) 的转移就是，每次枚举 负责 \(x\) 的节点 \(i\) ， 处理完后，取最小值
\(g_x = \min\) { \(dp_{x,i}\) } \((dis_{x, i} <= D_x)\)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1005;
int t, n, D[N], W[N], tot, head[N], nex[N << 1], to[N << 1], w[N << 1], dis[N][N];
void add(int x, int y, int z) {
to[++tot] = y, nex[tot] = head[x], head[x] = tot, w[tot] = z;
}
void dfs(int st, int x, int f) {
int ver;
for(int i = head[x]; i; i = nex[i]) {
ver = to[i];
if(ver == f) continue;
dis[st][ver] = dis[st][x] + w[i];
dfs(st, ver, x);
}
}
int dp[N][N], g[N];
void solve(int x, int f) {
int ver;
for(int i = head[x]; i; i = nex[i]) {
ver = to[i];
if(ver == f) continue;
solve(ver, x);
}
for(int i = 1; i <= n; i ++) {
if(dis[i][x] > D[x]) continue;
dp[x][i] = W[i];
for(int j = head[x]; j; j = nex[j]) {
ver = to[j];
if(ver == f) continue;
dp[x][i] += min(dp[ver][i] - W[i], g[ver]);
}
g[x] = min(g[x], dp[x][i]);
}
}
int main() {
int u, v, ww;
scanf("%d", &t);
while(t --) {
scanf("%d", &n);
tot = 0;
memset(head, 0, sizeof(head));
memset(dp, 0x3f, sizeof(dp));
memset(g, 0x3f, sizeof(g));
for(int i = 1; i <= n; i ++) scanf("%d", &W[i]);
for(int i = 1; i <= n; i ++) scanf("%d", &D[i]);
for(int i = 1; i < n; i ++) {
scanf("%d %d %d", &u, &v, &ww);
add(u, v, ww), add(v, u, ww);
}
for(int i = 1; i <= n; i ++) {
dis[i][i] = 0;
dfs(i, i, 0);
}
solve(1, 0);
printf("%d\n", g[1]);
}
return 0;
}
Rebuilding Roads
给定一棵 n 个节点的树，问最少删去多少条边，能够得到一个节点个数为 p 的连通块。
\(dp_{i,j}\) 表示 以 \(i\) 为根的子树 保留 \(j\) 个点联通的最小代价
重点在 \(dp\) 的初始条件的设置。
以及式子的小细节处理
$ dp_{i, j} = min(dp_{i, j}, dp_{i, j - k} + dp_{ver, k} - 1) $
因为 \(x\) 和 \(ver\) 之间相连是存在一条边的， 而那条边没有算进 \(dp_{ver, k}\) 中， 可能会在 \(dp_{x, j - k}\) 中被当成删边， 所以要 -1
初始值的设置真的好妙
最后答案统计也要注意，因为除树根之外的点在 \(DP\) 时都没有考虑 父亲， 所以最后还要额外删去 和父亲相连的那条边
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 155;
int n, p, rt, ans = 1e9, fa[N], tot, head[N], nex[N], to[N], dp[N][N], in[N], out[N];
void add(int x, int y) {
to[++tot] = y, nex[tot] = head[x], head[x] = tot;
}
int siz[N];
void dfs(int x) {
int ver;
siz[x] = 1;
for(int i = head[x]; i; i = nex[i]) {
ver = to[i];
dfs(ver);
siz[x] += siz[ver];
}
for(int i = head[x]; i; i = nex[i]) {
ver = to[i];
for(int j = siz[x]; j; j --) {
for(int k = 1; k < j; k ++) {
dp[x][j] = min(dp[x][j], dp[x][j - k] + dp[ver][k] - 1);
}
}
}
}
int main() {
int u, v;
memset(dp, 0x3f, sizeof(dp));
scanf("%d %d", &n, &p);
for(int i = 1; i < n; i ++) {
scanf("%d %d", &u, &v);
out[u] ++, in[v] ++;
add(u, v);
}
for(int i = 1; i <= n; i ++) {
if(!in[i]) rt = i;
dp[i][1] = out[i];
}
dfs(rt);
ans = dp[rt][p];
for(int i = 1; i <= n; i ++) ans = min(ans, dp[i][p] + 1);
printf("%d", ans);
return 0;
}