POI2016

Nadajniki

有一个妙妙树形 DP。

设 \(f_{i,0/1/2,0/1/2,0/1/2}\) 为第 \(i\) 个点，这个点上放没放，他儿子有没有放，他父亲有没有放。

然后硬转移就行了。

f[p][0][0][1]=f[p][0][0][2]=f[p][0][0][0]=0;
	f[p][1][0][0]=1;f[p][2][0][0]=2;
	for(int i=head[p];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(to[i],p);
		long long mn=inf;
		for(int j=0;j<=2;j++)
			for(int k=0;k<=2;k++)
				for(int l=0;l<=2;l++)
					mn=min(mn,f[v][j][k][l]),g[j][k][l]=f[p][j][k][l];
		f[p][2][0][0]+=mn;mn=inf;		
		for(int j=0;j<=2;j++)
			for(int k=0;k<=2;k++)
				for(int l=0;l<=1;l++)
					mn=min(mn,f[v][j][k][l]);
		f[p][1][0][0]+=mn;
		f[p][0][0][0]+=f[v][0][2][0];
		f[p][0][0][1]+=min(f[v][0][2][0],f[v][0][1][0]);
		f[p][0][0][2]+=min({f[v][0][2][0],f[v][0][1][0],f[v][0][0][0]});
		for(int j=0;j<=2;j++)
			f[p][0][1][j]=min(g[0][1][j]+min({f[v][0][2][0],f[v][0][1][0],j>0?f[v][0][0][0]:inf}),g[0][0][min(j+1,2)]+f[v][1][0][0]);
		for(int j=0;j<=2;j++)
			f[p][0][2][j]=min({g[0][2][j]+min({f[v][0][2][0],f[v][0][1][0],f[v][0][0][0],f[v][1][0][0],f[v][2][0][0]}),g[0][1][min(j+1,2)]+min(f[v][2][0][0],f[v][1][0][0]),g[0][0][2]+f[v][2][0][0]});
	}

后记

卡哇伊内

原文地址：http://www.cnblogs.com/cc0000/p/16790051.html