1421 秋静叶&秋穣子
在幻想乡,秋姐妹是掌管秋天的神明,作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一 起,自然会想到烤红薯。烤红薯需要很多的叶子,才能把红薯烤得很香,所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N), 并且规定了它们的选取顺序,刚好形成一颗有向树。在游戏过程中,两人从根节点开始,轮流取走红叶,当一个人取走节点i的红叶后,另一个人只能从节点i的儿 子节点中选取一个。当取到某个叶子时游戏结束,然后两人会比较自己得到的红叶数量。已知两人采用的策略不一样,静叶考虑在让穰子取得尽可能少的前提下,自 己取的最多;而穰子想得是在自己尽可能取得多的前提下,让静叶取得最少。在两人都采取最优策略的情况下,请你计算出游戏结束时两人的红叶数量。
游戏总是静叶先取,保证只存在一组解。
第1行:1个正整数N,表示红叶堆数
第2行:N个整数,第i个数表示第i堆红叶的数量num[i]
第3..N+1行:2个正整数u,v,表示节点u为节点v的父亲
第1行:2个整数,分别表示静叶取到的叶子数和穰子取到的叶子数
6
4 16 16 5 3 1
1 2
2 4
1 3
3 5
3 6
7 16
数据范围
对于30%的数据:1 ≤ N ≤ 100,1 ≤ num[i] ≤ 100
对于60%的数据:1 ≤ N ≤ 10,000,1 ≤ num[i] ≤ 10,000
对于100%的数据:1 ≤ N ≤ 100,000,1 ≤ num[i] ≤ 10,000
提示
样例解释:
首先静叶一定能取得节点1的4片红叶,留给穰子的是节点2和3,均为16片红叶。
若选取节点2则静叶下一次可以最多得到5片红叶,而选择3静叶最多也只能得到3片红叶,
所以此时穰子会选择节点3,故静叶最后得到的红叶数为7,穰子为16。
注意:
保证两人得到的红叶数在[0, 2^31-1]。
【思路】
树上DP+博弈
设f[i][0]表示以i为根的子树先手最优值,f[i][1]相应表示后手最优值。
因为不同的奕者有不同的策略,所以有
当dep为奇[静叶] (设dep[root]=1)
f[i][0]=f[k][1]+num[i]
f[i][1]=f[k][0]
k是i的儿子,且代表f[k][0]取最大时的k,当f[k][0]相同时,取f[k][1]最小。(穰子最优)
当dep为偶时[穰子]
f[i][0]=f[k][1]+num[i]
f[i][1]=f[k][0]
k是i的儿子,且代表f[k][1]取最小时的k,当f[k][1]相同时,取f[k][0]最大。(静叶最优)
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<iostream> 5 using namespace std; 6 7 const int N = 100000+10; 8 const int INF = 1e9+1e9; 9 10 vector<int> G[N]; 11 int n,f[N][2],num[N],in[N]; 12 13 void dfs(int u,int dep) { 14 int mn=INF,mx=0,k=0; 15 if(dep&1) { 16 for(int i=0;i<G[u].size();i++) { 17 int v=G[u][i]; 18 dfs(v,dep+1); 19 if(f[v][0]>mx || (f[v][0]==mx && f[v][1]<mn)) 20 mx=f[v][0] , mn=f[v][1] , k=v ; 21 } 22 f[u][0]=f[k][1]+num[u]; 23 f[u][1]=f[k][0]; 24 } 25 else { 26 for(int i=0;i<G[u].size();i++) { 27 int v=G[u][i]; 28 dfs(v,dep+1); 29 if(f[v][1]<mn || (f[v][1]==mn && f[v][0]>mx)) 30 mn=f[v][1] , mx=f[v][0] , k=v ; 31 } 32 f[u][0]=f[k][1]+num[u]; 33 f[u][1]=f[k][0]; 34 } 35 } 36 int read() { 37 char c=getchar(); 38 while(!isdigit(c)) c=getchar(); 39 int x=0; 40 while(isdigit(c)) 41 x=x*10+c-'0' , c=getchar(); 42 return x; 43 } 44 int main() { 45 n=read(); 46 for(int i=1;i<=n;i++) num[i]=read(); 47 int u,v; 48 for(int i=1;i<n;i++) { 49 u=read() , v=read(); 50 G[u].push_back(v); 51 in[v]++; 52 } 53 int root; 54 for(int i=1;i<=n;i++) 55 if(!in[i]) { root=i; break; } 56 dfs(root,1); 57 printf("%d %d",f[root][0],f[root][1]); 58 return 0; 59 }