文章目录

• 题目
• 分析
• 代码

题目

[SHOI 2015] 聚变反应炉

分析

对于树上一个点操作后对相邻节点产生影响的题目，DP 状态的定义需要考虑父节点的影响。

定义 DP 状态 d p [ u ] [ 0 / 1 ] dp[u][0/1] dp[u][0/1] 表示 u u u 的父亲节点 不给 u u u 传输能量 / / / 给 u u u 传输能量 时激发 u u u 的子树（包括 u u u）的最少代价。这样定义状态能知道父亲给自己传输的能量，再枚举子节点传输给自己的能量就可以转移了，然后涉及到“使子节点传输给自己的能量达到某一状态值的最小代价”，这是一个简单的树形背包问题。

代码

#include <bits/stdc++.h>
int Read() { 
int x = 0; char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + (c ^ 48), c = getchar();
return x;
}
const int MAXN = 100000;
const int MAXP = 2000;
const int MAXW = 5;
const int INF = 0x3f3f3f3f;
int N;
int D[MAXN + 5], C[MAXN + 5];
int Dp[MAXP + 5][2], Bag[2][MAXW * MAXP + 5];
std::vector<int> G[MAXN + 5];
void Dfs(const int &u, const int &f) { 
int tot = 0;
for (int v: G[u]) { 
if (v != f) { 
Dfs(v, u);
tot += C[v];
}
}
memset(Bag, 0x3f, sizeof Bag);
Bag[0][0] = 0;
int cur = 0, lst = 1;
for (int v: G[u]) { 
if (v != f) { 
cur ^= 1, lst ^= 1;
memset(Bag[cur], 0x3f, sizeof Bag[cur]);
for (int i = 0; i <= tot - C[v]; i++) { 
Bag[cur][i + C[v]] = std::min(Bag[cur][i + C[v]], Bag[lst][i] + Dp[v][0]);
Bag[cur][i] = std::min(Bag[cur][i], Bag[lst][i] + Dp[v][1]);
}
}
}
Dp[u][0] = Dp[u][1] = INF;
for (int i = 0; i <= tot; i++) { 
Dp[u][0] = std::min(Dp[u][0], std::max(Bag[cur][i], Bag[cur][i] + std::max(D[u]- i, 0)));
Dp[u][1] = std::min(Dp[u][1], std::max(Bag[cur][i], Bag[cur][i] + std::max(D[u] - C[f] - i, 0)));
}
}
int main() { 
N = Read();
int mxc = 0;
for (int i = 1; i <= N; i++)
D[i] = Read();
for (int i = 1; i <= N; i++)
mxc = std::max(mxc, C[i] = Read());
for (int i = 1; i < N; i++) { 
int u = Read(), v = Read();
G[u].push_back(v);
G[v].push_back(u);
}
if (mxc <= 1) { 
int Ans = 0;
for (int i = 1; i <= N; i++) { 
if (C[i] == 1) { 
Ans += D[i], D[i] = 0;
for (int v: G[i])
D[v]--;
}
}
for (int i = 1; i <= N; i++)
Ans += std::max(D[i], 0);
printf("%d", Ans);
return 0;
}
Dfs(1, 0);
printf("%d", Dp[1][0]);
return 0;
}

本文地址：https://blog.csdn.net/C20190102/article/details/110160305