【DP】树形DP 记忆化搜索

mac2022-06-30  132

DP中的树形DP,解决方法往往是记忆化搜索。显然,树上递推是很困难的。当然做得时候还是得把状态定义和转移方程写出来:dp[u][1/0]表示以u为根节点的树 涂(1) 或 不涂(0) 颜色的最少方案数。树上DP有两个经典问法:一条边两端至少有个一个端点涂色,问整个tree最少涂色次数;还有一种忘了。。。此题是前种问法。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2000; int first[maxn],tot; int dp[maxn][3]; int n,in[maxn]; struct Edge { int from,to,next; }E[maxn]; void init() { memset(first,-1,sizeof(first)); tot=0; memset(dp,-1,sizeof(dp)); memset(in,0,sizeof(in)); } void addedge(int u,int v) { E[tot].from=u; E[tot].to=v; E[tot].next=first[u]; first[u]=tot++; } int dfs(int u,bool flag) { if(flag){ if(dp[u][1]!=-1) return dp[u][1];} else { if(dp[u][0]!=-1) return dp[u][0];} dp[u][1]=1; dp[u][0]=0; for(int e=first[u];e!=-1;e=E[e].next) { int v=E[e].to; dp[u][1]+=min(dfs(v,true),dfs(v,false)); dp[u][0]+=dfs(v,true); } if(flag) return dp[u][1]; return dp[u][0]; } int main() { while(scanf("%d",&n)!=EOF) { init(); int node,num,a; for(int i=0; i<n; i++) { scanf("%d:(%d)",&node,&num); for(int i=0; i<num; i++) { scanf("%d",&a); in[a]++; addedge(node,a); } } int root; for(int i=0;i<n;i++) if(in[i]==0){root=i;break;} // cout<<"root "<<root<<endl; printf("%d\n",min(dfs(root,true),dfs(root,false))); // for(int i=0;i<n;i++) // cout<<dp[i][0]<<" "<<dp[i][1]<<endl; } }

转载于:https://www.cnblogs.com/Airplus/p/3869066.html

最新回复(0)