[BZOJ 4919][Lydsy1706月赛]大根堆

danihao123 posted @ 2018年4月15日 17:31 in 题解 with tags BZOJ 启发式合并 树形DP , 79 阅读
转载请注明出处:http://danihao123.is-programmer.com/

ao神啊这题,,,

很显然的思路是设计状态,然后线段树合并或者线段树启发式合并转移来优化一下,但是真的不好写……

考虑求LIS的那个二分+单调数组来做,那个东西的本质其实就是维护了一堆各种长度的断点一样的东西(考虑答案为\(n\),\(n - 1\)……的情况,在值的选取上各个情况之间会有断点)。那么我们就用一个multiset来维护断点,然后启发式合并即可。

考虑一棵子树,把根的子树进行合并,根加进来之后对断点会有何影响?那么考虑现在那个multiset里那个东西的后继(要lower_bound,因为如果有和根权值一样的点的话拐点不会发生变化。这里讨论有后继的情况),如果要取到那个点的长度的LIS的话,现在只需要小于等于根的权值的点就行了,取到这个点也不会使LIS变大(它不能和根共存),所以那个点就不是拐点了。并且无论是否出现这种情况,根那个点都会成为一个新的拐点。

然后DFS一遍就行啦。

代码:

/**************************************************************
    Problem: 4919
    User: danihao123
    Language: C++
    Result: Accepted
    Time:992 ms
    Memory:25648 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
const int maxn = 200005;
std::vector<int> G[maxn];
 
std::multiset<int> *st[maxn];
void merge(int x, int y) {
  if(st[x] -> size() < st[y] -> size()) std::swap(st[x], st[y]);
  while(st[y] -> size() > 0) {
    std::multiset<int>::iterator it = st[y] -> begin();
    int v = *it; st[y] -> erase(it);
    st[x] -> insert(v);
  }
}
int d[maxn];
void dfs(int x) {
  for(int i = 0; i < G[x].size(); i ++) {
    int v = G[x][i];
    dfs(v);
    merge(x, v);
  }
  std::multiset<int>::iterator it = st[x] -> lower_bound(d[x]);
  if(it != (st[x] -> end())) st[x] -> erase(it);
  st[x] -> insert(d[x]);
}
 
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int f; scanf("%d%d", &d[i], &f);
    G[f].push_back(i);
  }
  for(int i = 1; i <= n; i ++) {
    st[i] = new std::multiset<int>();
  }
  dfs(1);
  printf("%d\n", st[1] -> size());
  for(int i = 1; i <= n; i ++) {
    delete st[i];
  }
  return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter