The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1463 Strategic game 第二个树形DP

做第二的时候 一看就知道是个树形DP了 原来 树形DP的模式这么固定。。。但是那个递推方程确实还不能一下子想到,可能还需要积累些经验。
#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;
}



posted on 2010-03-08 00:38 abilitytao 阅读(1586) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理