「th04」秋静叶&秋穣子
Description
在幻想乡，秋姐妹是掌管秋天的神明，作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一起，自然会想到烤红薯。烤红薯需要很多的叶子，才能把红薯烤得很香，所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N)，并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走红叶，当一个人取走节点i的红叶后，另一个人只能从节点i的儿子节点中选取一个。当取到某个叶子时游戏结束，然后两人会比较自己得到的红叶数量。
已知两人采用的策略不一样.
|
1 2 3 |
<strong>静叶考虑在让穰子取得尽可能少的前提下，自己取的最多； 而穰子想得是在自己尽可能取得多的前提下，让静叶取得最少。</strong> |
在两人都采取最优策略的情况下，请你计算出游戏结束时两人的红叶数量。 游戏总是静叶先取，保证只存在一组解。
Input
第1行：1个正整数N，表示红叶堆数
第2行：N个整数，第i个数表示第i堆红叶的数量num[i]
第3..N+1行：2个正整数u,v，表示节点u为节点v的父亲
Output
第1行：2个整数，分别表示静叶取到的叶子数和穰子取到的叶子数
Sample Input
|
1 2 3 4 5 6 7 |
6 4 16 16 5 3 1 1 2 2 4 1 3 3 5 3 6 |
Sample Output
|
1 |
7 16 |
Hint
首先静叶一定能取得节点1的4片红叶，留给穰子的是节点2和3，均为16片红叶。若选取
节点2则静叶下一次可以最多得到5片红叶，而选择3静叶最多也只能得到3片红叶，所以
此时穰子会选择节点3，故静叶最后得到的红叶数为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
保证两人得到的红叶数在[0, 2^31-1]。
注意使用手工栈
「分析」
博弈论
在一棵有向树上最大-最小博弈。注意先后手的规则是不一样的。先手尽量让对方取少，而后手尽量让自己取多。注意要记录一个depth，以区分这个点是奇数还是偶数来判断先后手取得，以使用不同的规则。
我们定义一个数组F[MAXN][2]，F[i][0]表示以i为根的子树的先手最优值，F[i][1]表示以i为根的子树的后手最优值。
对于depth&1==1的情况：
F[i][0]=Num[i]+F[k][1];
F[i][1]=F[k][0];
k是i的儿子，k为max{F[k][0]}取得最大时的k，F[k][0]相同时，取F[k][1]最小的；
即我是先手（全局的先手），我只能取奇数深度的根节点，然后我的对手便会按照他的准则来取。他的准则便是让自己尽量多，所以他会在保证F[k][0]（他是全局的后手，那么他便是以k为根子树的先手）最大的情况下，来让F[k][1]最小，即让我尽量少。
对于depth&1==0的情况：
同样地：F[i][0]=Num[i]+F[k][1];
F[i][1]=F[k][0];
k是i的儿子，k为min{F[k][1]}取得最小时的k，F[k][1]相同时，取F[k][0]最大的。
即我是后手（全局的后手），我只能取偶数深度的根节点，而当前节点深度正好为偶数。我对手的准则让我尽量少，所以他会在保证F[k][1]尽量小的情况下（我是全局后手，又k为奇数节点，所以我为k的后手），让F[k][0]尽量大，即让我的对手尽量多。
|
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 |
#include<cstdio> #include<iostream> #include<cstring> #define inf 0x7fffffff using namespace std; int head[100001],v[100001],f[100001][2];//先手/后手 bool r[100001],de[100001]; int root,n,cnt; struct data{int to,next;}e[100001]; void ins(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void dfs(int x) { bool d=de[x]; int mn=inf,mx=0,k=0; if(d) { for(int i=head[x];i;i=e[i].next) { int t=e[i].to;de[t]=d^1; dfs(t); if(f[t][0]>mx||(f[t][0]==mx&&f[t][1]<mn)) {mx=f[t][0];k=t;mn=f[t][1];} } f[x][0]=f[k][1]+v[x]; f[x][1]=f[k][0]; } else { for(int i=head[x];i;i=e[i].next) { int t=e[i].to;de[t]=d^1; dfs(t); if(f[t][1]<mn||(f[t][1]==mn&&f[t][0]>mx)) {mn=f[t][1];k=t;mx=f[t][0];} } f[x][0]=f[k][1]+v[x]; f[x][1]=f[k][0]; } } int main() { //freopen("aki.in","r",stdin); //freopen("aki.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); r[v]=1; ins(u,v); } for(int i=1;i<=n;i++)if(!r[i])root=i; de[root]=1; dfs(root); printf("%d %d",f[root][0],f[root][1]); //system("pause"); return 0; } |
这样做可以得九十分，其余俩点会栈溢出
于是我们要手动搞一个栈
|
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 |
#include<cstdio> #include<iostream> #include<cstring> #define inf 0x7fffffff using namespace std; int head[100001],v[100001],f[100001][2],s[100001];//先手/后手 bool r[100001],c[100001],vis[100001],de[100001]; int top,root,n,cnt; struct data{int to,next;}e[100001]; void ins(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void dfs() { while(top) { int x=s[top];bool d=de[top]; if(!c[x]) { f[x][0]=v[x]; top--;continue; } if(!vis[x]) { for(int i=head[x];i;i=e[i].next) { int t=e[i].to; s[++top]=t;de[top]=d^1; } vis[x]=1;continue; } int mn=inf,mx=0,k=0; if(d) { for(int i=head[x];i;i=e[i].next) { int t=e[i].to; if(f[t][0]>mx||(f[t][0]==mx&&f[t][1]<mn)) {mx=f[t][0];k=t;mn=f[t][1];} } } else { for(int i=head[x];i;i=e[i].next) { int t=e[i].to; if(f[t][1]<mn||(f[t][1]==mn&&f[t][0]>mx)) {mn=f[t][1];k=t;mx=f[t][0];} } } f[x][0]=f[k][1]+v[x]; f[x][1]=f[k][0]; top--; } } int main() { //freopen("aki.in","r",stdin); //freopen("aki.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=n-1;i++) { int u,v; scanf("%d%d",&u,&v); r[v]=1;c[u]=1; ins(u,v); } for(int i=1;i<=n;i++)if(!r[i])root=i; s[++top]=root;de[top]=1; dfs(); printf("%d %d",f[root][0],f[root][1]); //system("pause"); return 0; } |
OI 课件=>
