题解：P7201 [COCI 2019/2020 #1] Džumbus
cjrqwq
·
·
题解
前言
建议评蓝？讨论问题的方式是较套路的。
思路
首先发现这是一个森林，用超级源点连一下就变成了树。
那么对于儿子节点 $v$，考虑将 $v$ 和已经遍历过的子树和 $u$ 进行讨论，我们令 $s = i+j$，$i$ 表示已经遍历过的子树和 $u$ 中有 $i$ 的贡献，$j$ 表示在以 $v$ 为根的子树中的贡献：
### 当更新后的 $u$ 无贡献时
那 $v$ 节点可以有，也可以没有贡献。所以枚举 $i,j$， 用 $f_{v,0,j}$ 和 $f_{v,1,j}$ 更新 $f_{u,0,i+j}$。**以下的讨论也是这种形式，就不写出来了，保证代码和思路一致。**
### 当更新后的 $u$ 有贡献时
- 以前的 $u$ 没有贡献，但是现在有了。说明子树 $v$ 是要有贡献的。这里又可以讨论出两种情况：本来 $u,v$ 都没贡献，将 $u,v$ 都贡献；本来 $v$ 有贡献，$u$ 没贡献，把 $u$ 贡献。**注意：两种情况是不一样的，一次贡献 $u,v$，$v$ 的儿子节点不一定要贡献，但如果 $v$ 本来就有贡献，$v$ 的儿子也是有贡献的。这关乎到动态规划的特点，子问题的决策是不能关系到原问题的决策的**。
- 以前的 $u$ 有贡献，这里也是两种情况：不改变 $v$ 的贡献；本来 $v$ 无贡献，改为有贡献。
---
然后答案没有单调性，解决方法很多。我用的单调栈，也有其他很短的写法，就不赘述了。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e3+10, inf = 1e18;
int fa[N];
int fd (int x) {return fa[x] == x ? x : fa[x] = fd(fa[x]);}
void merge (int x,int y) {fa[fd(x)] = fd(y);}
vector<int>e[N];
int f[N][2][N];
int tmp[2][N],sz[N],w[N];
void dfs (int u,int fa) {
sz[u] = 1;
f[u][1][0] = 0;
for (int v : e[u]) {
if (v == fa) {continue;}
dfs(v,u);
copy(f[u][0],f[u][0]+sz[u]+1,tmp[0]);
copy(f[u][1],f[u][1]+sz[u]+1,tmp[1]);
for (int i=0;i<=sz[u];i++) {
for (int j=1;j<=sz[v];j++) {
f[u][1][i+j] = min(f[u][1][i+j], tmp[1][i] + min(f[v][0][j], f[v][1][j]));
f[u][0][i+j] = min ( {
f[u][0][i+j],
i >= 1 ? tmp[1][i-1] + f[v][1][j-1] + w[u] + w[v] : inf,
i >= 1 ? tmp[1][i-1] + f[v][0][j] + w[u] : inf,
tmp[0][i] + min(f[v][0][j], f[v][1][j]),
tmp[0][i] + f[v][1][j-1] + w[v]
});
}
}
sz[u] += sz[v];
}
}
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n,m,q;cin>>n>>m;
iota(fa+1,fa+n+1,1);
for (int i=1;i<=n;i++) cin>>w[i];
for (int i=1,u,v;i<=m;i++) {
cin>>u>>v;
e[u].push_back(v), e[v].push_back(u);
merge(u,v);
}
int root = n+1;
for (int i=1;i<=n;i++) {
if(i == fd(i)) e[root].push_back(i), e[i].push_back(root);
}
for (int i=0;i<N;i++) { // memset 0x3f w+w+f+f 会溢出
for (int j=0;j<2;j++) {
for (int k=0;k<N;k++) {
f[i][j][k] = inf;
}
}
}
dfs(root,root);
vector<pair<int,int>>Qu(1);
for (int i=1;i<=n;i++) {
if (f[root][1][i] <= inf) {
while (!Qu.empty() && Qu.back().first > f[root][1][i]) Qu.pop_back();
Qu.push_back({f[root][1][i], i});
}
}
cin >> q;
while (q--) {
int x; cin>>x;
int L = 0, R = Qu.size();
while (L + 1 < R) {
int mid = L + R >> 1;
if (Qu[mid].first <= x) L = mid;
else R = mid;
}
cout << Qu[L].second << '\n';
}
return 0;
}
```