分类 最长子序列问题 下的文章

BZOJ 4919: [Lydsy1706月赛]大根堆

Solution本质上树上问题和链上的最长子序列区别不大,只需要将数组启发式合并就可以了,用 set 就可以。Description给定一棵n个节点的有根树,编号依次为1到n,其中1号点为根节点。每个点有一个权值v_i。你需要将这棵树转化成一个大根堆。确切地说,你需要选择尽可能多的节点,满足大根堆的性质:对于任意两个点i,j,如果i在树上是j的祖先,那么v_i>v_j。请计算可选的最多的点数,注意这些点不必形成这棵树的一个连通子树。Input第一行包含一个正整数n(1<=n<=200000),表示节点的个数。接下来n行,每行两个整数v_i,p_i(0<- 阅读剩余部分 -

BZOJ 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

题目描述为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐。每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排,晚饭前的排队成了一个大麻烦。 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来,卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后,FJ找到了一种简单些的方法:奶牛们不动,他沿着队伍从头到尾走一遍把那- 阅读剩余部分 -