如何用树形动态规划解决CQOI2009叶子染色问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计423个文字，预计阅读时间需要2分钟。
【CQOI2009】叶子的颜色由 \( f(x) \) 决定，\( f(x) \) 的值分为 \( 0 \), \( 1 \), \( 2 \) 三类，分别表示 \( x \) 点染为黑、白、不染。要找出使 \( x \) 点染为黑、白、不染的子树满足条件的最小颜色点数，然后是注意初始化ovo。
[CQOI2009]叶子的染色
\(f[x][0/1/2]\)分别表示x点染为黑/白/不染x为根的子树满足条件的最小染色点数
然后就是注意初始化ovo
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define Max(x,y) ((x)>(y)?(x):(y)) #define Min(x,y) ((x)>(y)?(y):(x)) const int N=10000+5,M=2e5+5,inf=0x3f3f3f3f,P=19650827; int n,m,rt,c[N],f[N][4],in[N]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,nxt;}e[N<<1]; void add(int u,int v){ e[++tot]=(edge){v,head[u]},head[u]=tot; } void dfs(int u,int fa){ if(u<=n) f[u][c[u]]=1,f[u][c[u]^1]=inf,f[u][2]=1; else f[u][0]=f[u][1]=1; for(int i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(v==fa) continue; dfs(v,u); f[u][0]+=Min(f[v][2],Min(f[v][0]-1,f[v][1])); f[u][1]+=Min(f[v][2],Min(f[v][0],f[v][1]-1)); f[u][2]+=Min(f[v][2],Min(f[v][0],f[v][1])); } } int main(){ freopen("in2.txt","r",stdin); //freopen("xor.out","w",stdout); rd(m),rd(n); for(int i=1;i<=n;++i) rd(c[i]); for(int i=1,u,v;i<m;++i){ rd(u),rd(v),add(u,v),add(v,u); } rt=n+1; dfs(rt,0); printf("%d",Min(f[rt][0],Min(f[rt][1],f[rt][2]))); return 0; }
本文共计423个文字，预计阅读时间需要2分钟。
【CQOI2009】叶子的颜色由 \( f(x) \) 决定，\( f(x) \) 的值分为 \( 0 \), \( 1 \), \( 2 \) 三类，分别表示 \( x \) 点染为黑、白、不染。要找出使 \( x \) 点染为黑、白、不染的子树满足条件的最小颜色点数，然后是注意初始化ovo。
[CQOI2009]叶子的染色
\(f[x][0/1/2]\)分别表示x点染为黑/白/不染x为根的子树满足条件的最小染色点数
然后就是注意初始化ovo
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define Max(x,y) ((x)>(y)?(x):(y)) #define Min(x,y) ((x)>(y)?(y):(x)) const int N=10000+5,M=2e5+5,inf=0x3f3f3f3f,P=19650827; int n,m,rt,c[N],f[N][4],in[N]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,nxt;}e[N<<1]; void add(int u,int v){ e[++tot]=(edge){v,head[u]},head[u]=tot; } void dfs(int u,int fa){ if(u<=n) f[u][c[u]]=1,f[u][c[u]^1]=inf,f[u][2]=1; else f[u][0]=f[u][1]=1; for(int i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(v==fa) continue; dfs(v,u); f[u][0]+=Min(f[v][2],Min(f[v][0]-1,f[v][1])); f[u][1]+=Min(f[v][2],Min(f[v][0],f[v][1]-1)); f[u][2]+=Min(f[v][2],Min(f[v][0],f[v][1])); } } int main(){ freopen("in2.txt","r",stdin); //freopen("xor.out","w",stdout); rd(m),rd(n); for(int i=1;i<=n;++i) rd(c[i]); for(int i=1,u,v;i<m;++i){ rd(u),rd(v),add(u,v),add(v,u); } rt=n+1; dfs(rt,0); printf("%d",Min(f[rt][0],Min(f[rt][1],f[rt][2]))); return 0; }