BZOJ1369/LG4395 「BOI2003」Gem 树形DP

问题描述

题解

发现对于结点 \(x\) ，其父亲，自己，和所有的孩子权值不同，共 \(3\) 类，从贪心的角度考虑，肯定是填 \(1,2,3\) 这三种。

于是套路树形DP，设 \(opt[x][1/2/3]\) 代表以 \(x\) 为根的子树中，且 \(x\) 标为 \(0/1/2\) 的最小值。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=10007;

const int maxm=20007;

int n;

int Head[maxn],to[maxm],Next[maxm],tot;

int opt[maxn][4];

void add(int x,int y){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;

}

void dp(int x,int f){

	for(int i=1;i<=3;i++) opt[x][i]=i;

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(y==f) continue;

		dp(y,x);

		opt[x][1]+=min(opt[y][2],opt[y][3]);

		opt[x][2]+=min(opt[y][1],opt[y][3]);

		opt[x][3]+=min(opt[y][1],opt[y][2]);

	}

}

int main(){

	read(n);

	for(int i=1,x,y;i<n;i++){

		read(x);read(y);

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

	}

	dp(1,0);

	printf("%d\n",min(opt[1][1],min(opt[1][2],opt[1][3])));

	return 0;

}

巴特西

BZOJ1369/LG4395 「BOI2003」Gem 树形DP

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章