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
