Categories

HOJ 2500 Party at Hali-Bula

设F[I]表示邀请I的最大值
设G[I]表示不邀请I的最大值

F[I] = ∑{G[I.sons]}
G[I] = ∑{Max(F[I.sons],G[I.sons]}}

第一次写Tree DP,写得比较恶心.因为一个下标写错,查了N久才找出错误.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
#define msize 300
using namespace std;
 
struct node
{
    string name;
    int staff[msize]; //staff[0]存储有多少个下属
}guest[msize];
 
int n;
string s1,s2;
int cnt; //一共有多少个不同的guest
int f[msize][2];
bool status[msize][2];
 
int dp(int i,bool flag); //flag==true表示选i,flag==false表示不选i
 
int main()
{
    while (cin>>n)
    {
        if (n==0) break;
 
        cin>>guest[0].name;
        guest[0].staff[0]=0;
        cnt=1;
        for (int i=1;i<n;i++)
        {
            cin>>s1>>s2;
 
            int j,k;
            for (j=0;j<cnt;j++) if (guest[j].name==s2) break;
            if (j==cnt)
            {
                guest[cnt].name=s2;
                guest[cnt++].staff[0]=0;
            }
 
            for (k=0;k<cnt;k++) if (guest[k].name==s1) break;
            if (k==cnt)
            {
                guest[cnt].name=s1;
                guest[cnt++].staff[0]=0;
            }
 
            guest[j].staff[0]++;
            guest[j].staff[guest[j].staff[0]]=k;
        }
 
        memset(f,-1,sizeof(f));
        memset(status,false,sizeof(status));
        int a=dp(0,true);
        int b=dp(0,false);
 
        cout<<max(a,b)<<" ";
        if (a==b) cout<<"No"<<endl;
        else if (a>b)
        {
            if (status[0][true]) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
        else
        {
            if (status[0][false]) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
 
    return 0;
}
 
int dp(int n,bool flag) //flag==true表示选i,flag==false表示不选i
{
    if (f[n][flag]!=-1) return f[n][flag];
    //if (guest[n].staff[0]==0) return flag;
 
    int sum;
    if (flag)
    {
        sum=0;
        for (int i=1;i<=guest[n].staff[0];i++)
        {
            int idx=guest[n].staff[i];
            sum += dp(idx,false);
            status[n][flag] |= status[idx][false];
        }
        f[n][flag]=sum+1;
    }
    else
    {
        sum=0;
        for (int i=1;i<=guest[n].staff[0];i++)
        {
            int idx=guest[n].staff[i];
            int a=dp(idx,true),b=dp(idx,false);
            if (a==b) status[n][flag]=true;
            else if (a>b) status[n][flag] |= status[idx][true];
            else status[n][flag] |= status[idx][false];
            sum += max(a,b);
        }
        f[n][flag]=sum;
    }
 
    return f[n][flag];
}

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*