归属简单树形DP 挺简单的 跟第一道一样 就是我跑偏了题意。。以为要覆盖点 纠结啊 推了N久 推不出啊 然后就郁闷了 打了局游戏 边想边打 实在想不出 看下题解 跑偏了
分两种情况D 方程见代码
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 2010
int f[N];
struct node
{
int f,ch,m1,m0,br;
void init()
{
f = m0 =ch = br =;
m1 = ;
}
}tr[N];
void dfs(int u)
{
int child = tr[u].ch;
while(child)
{
dfs(child);
tr[u].m1+=min(tr[child].m0,tr[child].m1);
tr[u].m0+=tr[child].m1;
child = tr[child].br;
}
}
int main()
{
int i,j,n,u,m,v;
while(scanf("%d",&n)!=EOF)
{
memset(f,,sizeof(f));
for(i = ; i <= n ; i++)
{
scanf("%d:(%d)",&u,&m);
u++;
if(!f[u])
tr[u].init();
for(j = ; j <= m ; j++)
{
scanf("%d",&v);
v++;
tr[v].init();
tr[v].f = u;
tr[v].br = tr[u].ch;
tr[u].ch = v;
f[v] = ;
}
}
for(i = ; i <= n ; i++)
{
if(!f[i])
break;
}
dfs(i);
cout<<min(tr[i].m0,tr[i].m1)<<endl;
}
return ;
}