首页 > 代码库 > 【BZOJ 4169】 4169: Lmc的游戏 (树形DP)
【BZOJ 4169】 4169: Lmc的游戏 (树形DP)
4169: Lmc的游戏
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 44 Solved: 25Description
RHL有一天看到lmc在玩一个游戏。"愚蠢的人类哟,what are you doing",RHL说。"我在玩一个游戏。现在这里有一个有n个结点的有根树,其中有m个叶子结点。这m个叶子从1到m分别被给予了一个号码,每个叶子的号码都是独一无二的。一开始根节点有一个棋子,两个玩家每次行动将棋子移动到当前节点的一个儿子节点。当棋子被移动到某个叶节点的时候游戏结束,这个叶节点的号码即为该局游戏的result。先手的玩家要最大化result,后手的玩家要最小化这个result。""你不先问一下我是谁吗 = =""那么,who are you""我是这个世界的创造者,维护者和毁灭者,整个宇宙的主宰,无所不知,无所不能的,三个字母都大写的RHL。""既然你这么厉害,那你一定知道,在两个玩家都无限聪明的情况下,在树的形态已知的情况下,在叶子的编号可以任意安排的情况下,游戏的result最大是多少咯。"Input
输入数据第一行有一个正整数n,表示结点的数量。n<=200000接下来n-1行,每行有两个正整数u和v,表示的父亲节点是u。Output
输出一行2个非负整数,分别表示result的最大值和最小值。Sample Input
5
1 2
1 3
2 4
2 5Sample Output
3 2
【样例解释】
有3,4,5三个叶子。若令3号叶子的编号是3,则先手可以移到3号结点,故result最大是3。若3号叶子的编号是2,
则先手可以移到3号结点,故result最小是2.HINT
Source
【分析】
【想出来了】
然而网上没有题解,我就写写,好少人做这题。
如果你是先手的话,你肯定选子树里面能得到答案最大的那个走。
如果你是后手的话,你肯定选子树里面能得到答案最小的那个走。
$mx[i]$表示走$i$这棵子树,$result$最大是多少(指的是,你在子树填入$a1<a2<a3...$最大是排名第几的,下同)。
$mn[i]$表示走$i$这棵子树,$result$最小是多少。
当你是偶数层($root$这层视为0),即先手操作,你应该是$result=max(子树1,子树2,子树3....)$
最大化$result$显然是让各子树的$result$都最大化,然后呢,因为你取的是$max$,所以最好就是把其他子树都堆在前面,然后让$mx$最大的子树放在最后。
即$mx[x]=max(mx[x],sm[x]-(sm[y]-mx[y]))$; (sm是子树里面的叶子节点个数)
最小化$result$就是让子树都先选$1~mn$放在前面,即$mn[x]+=mn[y]$;
其实解题本质,就是你自己想想怎么样分配最好嘛。。
当$dep$为奇数,是$result=min(max(),max(),...)$这样的形式如下
$mx[x]=\sum (mx[y]-1) +1$;
View Code
$mn[x]=min(mn[x],mn[y])$;
也不知道怎么说。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define INF 0xfffffff 8 #define Maxn 200010 9 10 int mymax(int x,int y) {return x>y?x:y;} 11 int mymin(int x,int y) {return x<y?x:y;} 12 13 int mx[Maxn],mn[Maxn]; 14 15 struct node 16 { 17 int x,y,next; 18 }t[Maxn]; 19 int first[Maxn],len; 20 void ins(int x,int y) 21 { 22 t[++len].x=x;t[len].y=y; 23 t[len].next=first[x];first[x]=len; 24 } 25 26 int sm[Maxn]; 27 void dfs(int x,int dep) 28 { 29 sm[x]=0; 30 if(first[x]==0) 31 { 32 sm[x]=1; 33 mn[x]=mx[x]=1;return; 34 } 35 for(int i=first[x];i;i=t[i].next) 36 { 37 int y=t[i].y; 38 dfs(y,dep^1); 39 sm[x]+=sm[y]; 40 } 41 mx[x]=0;mn[x]=0; 42 if(dep) mx[x]=1,mn[x]=INF; 43 for(int i=first[x];i;i=t[i].next) 44 { 45 int y=t[i].y; 46 if(!dep) 47 { 48 mx[x]=mymax(mx[x],sm[x]-(sm[y]-mx[y])); 49 mn[x]+=mn[y]; 50 } 51 else 52 { 53 mx[x]+=mx[y]-1; 54 mn[x]=mymin(mn[x],mn[y]); 55 } 56 } 57 } 58 59 int main() 60 { 61 int n; 62 scanf("%d",&n); 63 int rt=0; 64 for(int i=1;i<=n;i++) rt+=i; 65 len=0; 66 memset(first,0,sizeof(first)); 67 for(int i=1;i<n;i++) 68 { 69 int x,y; 70 scanf("%d%d",&x,&y); 71 ins(x,y); 72 rt-=y; 73 } 74 dfs(rt,0); 75 printf("%d %d\n",mx[rt],mn[rt]); 76 return 0; 77 }
【BZOJ 4169】 4169: Lmc的游戏 (树形DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。