题解：P7201 [COCI 2019/2020 #1] Džumbus

前言

建议评蓝？讨论问题的方式是较套路的。

思路

首先发现这是一个森林，用超级源点连一下就变成了树。

n \le 10^3

，引导我们进行背包。定义

f_{u,0/1,s}

表示以

u

为根的子树，节点

u

不是或是分享答案的朋友（以下称“有贡献”），且总共有

s

个节点有贡献。（

f_{u,0,s}

表示有贡献，

f_{u,1,s}

表示无贡献）。

那么对于儿子节点

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;
}

题解：P7201 [COCI 2019/2020 #1] Džumbus

文章操作

前言

思路

当更新后的 $u$ 无贡献时

当更新后的 $u$ 有贡献时

代码

相关推荐

评论

题解：P7201 [COCI 2019/2020 #1] Džumbus

文章操作

前言

思路

当更新后的 uuu 无贡献时

当更新后的 uuu 有贡献时

代码

相关推荐

评论

当更新后的 $u$ 无贡献时

当更新后的 $u$ 有贡献时