hdu 6772 Lead of Wisdom

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int maxn =1e5+10;
 6 const int mod=1e9+7;
 7 int n,k;
 8 vector<int>E[55];
 9 int nxt[55];
10 
11 ll ans=0;
12 
13 
14 void dfs(int t,int a,int b,int c,int d)
15 {
16     int u=nxt[t];
17     if(u==100)
18     {
19         ll sum=1ll*(100+a)*(100+b)*(100+c)*(100+d);
20         ans=max(ans,sum);
21         return;
22     }
23     int len=E[u].size();
24     for(int i=0;i*4<len;i++)
25     {
26         int ta=a+E[u][0+i*4];
27         int tb=b+E[u][1+i*4];
28         int tc=c+E[u][2+i*4];
29         int td=d+E[u][3+i*4];
30         dfs(t+1,ta,tb,tc,td);
31     }
32 
33 }
34 void init()
35 {
36     for(int i=1;i<=50;i++)
37         E[i].clear();
38     memset(nxt,0,sizeof(nxt));
39     ans=0;
40 }
41 
42 set<int>s;
43 
44 int main()
45 {
46     ios::sync_with_stdio(false);
47     cin.tie(0);
48     int t;
49     cin>>t;
50     while(t--)
51     {
52         cin>>n>>k;
53         set<int>s;
54         init();
55         for(int i=1;i<=n;i++)
56         {
57             int t,a,b,c,d;
58             cin>>t>>a>>b>>c>>d;
59             s.insert(t);
60             E[t].pb(a);
61             E[t].pb(b);
62             E[t].pb(c);
63             E[t].pb(d);
64         }
65         int tot=0;
66         for(auto &v:s)
67         {
68             nxt[++tot]=v;
69         }
70         nxt[++tot]=100;
71         dfs(1,0,0,0,0);
72         cout<<ans<<‘\n‘;
73 
74 
75     }
76 
77 }