首页 > 代码库 > BZOJ 2466: [中山市选2009]树
BZOJ 2466: [中山市选2009]树
Sol
树形DP.
听说有非常神奇的高斯消元的做法...orz...
然而我只会 \(O(n)\) 的树形DP.
首先一个点的状态只于他的父节点和子树有关,跟他 子树的子树 和 父亲的父亲 都没有任何关系.
这样就可以DP了.
\(f[i][0/1][0/1]\) 表示\(i\)节点,点了 \(0/1\) 次,状态是 \(0/1\) (暗或亮).
然后就瞎转移就可以了,具体看代码吧.
Code
/************************************************************** Problem: 2466 User: BeiYu Language: C++ Result: Accepted Time:4 ms Memory:1292 kb****************************************************************/ #include<cstdio>#include<vector>#include<cstring>#include<iostream>using namespace std; const int N = 105;const int INF = 0x03ffffff; int n;int f[N][2][2];vector<int> g[N]; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; } void DP(int u,int fa){// if(fa&&g[u].size()==1){ f[u][0][0]=0,f[u][0][1]=INF,f[u][1][0]=INF,f[u][1][1]=1;return; } int t0=0,t1=INF,t2=INF,t3=0; for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i])!=fa){ DP(v,u); int s0=t0,s1=t1,s2=t2,s3=t3; t0=min(s1+f[v][1][1],s0+f[v][0][1]); t1=min(s1+f[v][0][1],s0+f[v][1][1]); t2=min(s3+f[v][1][0],s2+f[v][0][0]); t3=min(s3+f[v][0][0],s2+f[v][1][0]); } f[u][0][0]=t0,f[u][0][1]=t1; f[u][1][0]=t2+1,f[u][1][1]=t3+1;}int main(){// freopen("in.in","r",stdin); for(;n=in();){ for(int i=1;i<N;i++) g[i].clear(); for(int i=1,u,v;i<n;i++) u=in(),v=in(),g[u].push_back(v),g[v].push_back(u); DP((n+1)/2,0); cout<<min(f[(n+1)/2][1][1],f[(n+1)/2][0][1])<<endl;// DP(1,0);// cout<<min(f[1][1][1],f[1][0][1])<<endl;// for(int i=1;i<=n;i++)// cout<<i<<"->"<<f[i][0][0]<<" "<<f[i][0][1]<<" "<<f[i][1][0]<<" "<<f[i][1][1]<<endl;// cout<<"*******************"<<endl; }return 0;}
BZOJ 2466: [中山市选2009]树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。