做第二的時(shí)候 一看就知道是個(gè)樹形DP了 原來 樹形DP的模式這么固定。。。但是那個(gè)遞推方程確實(shí)還不能一下子想到，可能還需要積累些經(jīng)驗(yàn)。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>hash[1500];
int n;
int s[1500];
int dp[1500][2];
int root;
void dfs(int x)
{
int i,j;
int len=hash[x].size();
for(i=0;i<len;i++)
dfs(hash[x][i]);
if(len==0){dp[x][0]=0;dp[x][1]=1;}
else
{
for(i=0;i<len;i++)
{
dp[x][0]+=dp[hash[x][i]][1];
dp[x][1]+=min(dp[hash[x][i]][0],dp[hash[x][i]][1]);
}
dp[x][1]++;
}
}
int main()
{
int v,t,num;
int i,j;
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
memset(s,0,sizeof(s));
for(i=0;i<n;i++)
hash[i].clear();
for(i=1;i<=n;i++)
{
scanf("%d:(%d)",&v,&num);
for(j=1;j<=num;j++)
{
scanf("%d",&t);
hash[v].push_back(t);
s[t]=1;
}
}
for(i=0;i<n;i++)
if(s[i]==0){root=i;break;}
dfs(root);
printf("%d\n",min(dp[root][0],dp[root][1]));
}
return 0;
}