[JZOJ5400]:Repulsed（贪心+树形DP）

题目描述

　　小$w$心里的火焰就要被熄灭了。
　　简便起见，假设小$w$的内心是一棵$n-1$条边，$n$个节点的树。
　　现在你要在每个节点里放一些个灭火器，每个节点可以放任意多个。
　　接下来每个节点都要被分配给一个至多$k$条边远的灭火器，每个灭火器最多能分配给$s$个节点。
　　至少要多少个灭火器才能让小$w$彻底死心呢？

输入格式

　　第一行三个整数$n,s,k$。
　　接下来$n-1$行每行两个整数表示一条边。

输出格式

　　一行一个整数表示答案

样例

样例输入：

10 10 3
1 8
2 3
1 5
2 4
1 2
8 9
8 10
5 6
5 7

样例输出：

数据范围与提示

　　对于$20\%$的数据满足$n\leqslant 100,k\leqslant 2$。
　　对于另外$20\%$的数据满足$k=1$。
　　对于另外$20\%$的数据满足$s=1$。
　　对于$100\%$的数据满足$n\leqslant 10^5,k\leqslant 20,s\leqslant 10^9$。

题解

先来考虑贪心，依次选还没有被覆盖的深度最大的点一定更优，这个用一个堆维护就好啦。

但是可能存在灭火器交集很大的情况。

再来考虑$DP$，设$G[x][k]$表示$x$下面距离为$k$的需要灭火器的房间数，$F[x][k]$表示$x$下面距离为$k$的多余灭火器数。

首先$G[x][k]$要与$F[x][0]$匹配。

还要注意可以跨国$LCA$，所以$G[x][i]$也可以与$F[x][k-i]$匹配，$G[x][i]$与$F[x][k-i-1]$匹配。

那么有转移：

$$F[u][i]=\sum\limits_vF[v][i-1]$$

$$G[u][i]=\sum\limits_vG[v][i+1]$$

初始化$F[x][i]=G[x][i]=1$即可。

匹配的时候用指针维护就好了。

时间复杂度：$\Theta(nk)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to;}e[200000];

int head[100001],cnt;

int n,s,k;

int f[100001][21],g[100001][21];

bool vis[100001];

int ans,sum;

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void dfs(int x)

{

	vis[x]=1;

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to);

		for(int j=1;j<=k;j++)

		{

			f[x][j]+=f[e[i].to][j-1];

			g[x][j-1]+=g[e[i].to][j];

			g[x][j-1]=min(g[x][j-1],n);

		}

	}

	f[x][0]++;

	if(f[x][k])

	{

		int tmp=(ceil)((double)f[x][k]/s);

		ans+=tmp;

		g[x][k]+=min(tmp*s,n)-f[x][k];

		f[x][k]=0;

	}

	int fail=k;

	for(int i=k;~i;i--)

		while(f[x][i]&&fail>=i)

		{

			int flag=min(f[x][i],g[x][fail]);

			f[x][i]-=flag;g[x][fail]-=flag;

			if(!g[x][fail])fail--;

		}

}

int main()

{

	scanf("%d%d%d",&n,&s,&k);

	for(int i=1;i<n;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		add(x,y);add(y,x);

	}

	dfs(1);

	for(int i=0;i<=k;i++)sum+=f[1][i];

	ans+=(ceil)((double)sum/s);

	printf("%d",ans);

	return 0;

}

rp++

巴特西