HDU 5575 Discover Water Tank 并查集树形DP

题意：

有一个水槽，边界的两块板是无穷高的，中间有n-1块隔板（有高度），现有一些条件(i,y,k)，表示从左到右数的第i列中，在高度为(y+0.5)的地方是否有水（有水：k = 1），问最多能同时满足多少个条件。范围：1e5

分析：

考虑按隔板的高度从小到大合并隔板相邻的两列，合并的时候新开一个节点，这个可以用并查集来做。

这样合并过来就会得到一棵树，接下来就考虑如何把询问塞进去，然后做树形DP。

对于一个询问，我们需要把它存入第i列对应的叶节点上的某个父亲那里去，这个可以用vector来做，具体是哪个父亲可以倍增地找（当然预处理的时候要求一遍lca），即高度恰好在某个隔板下，这样就可以树形DP了。

树形DP：设d[i]表示树上以节点i的子树最多能满足的条件数，f[i]表示树上以节点i为子树中节点i有水能满足的条件数，emp[i]表示树上的节点i处没有水能满足的条件数。

对于d[i]，节点i处没水，就直接转移emp[i]+d[son[i][0]]+d[son[i][1]]；节点i处有水，则其子树必然有水，而节点i处的条件的高度y也不是单一的，这样我们只需求一个最大的前缀和（即水淹到哪一个高度，满足的条件有多少，求一个最大值）就可以了。

对于f[i]，f[son[i][0]]+f[son[i][1]]+节点i处有水的条件数。

答案为d[rt]。

-----------------------------------------------------------------------------------------------------------------------------------

另外网上的似乎有一种更容易写的方法，直接把询问建树，当然还是按列合并，算法的思路也是一致的，但是树形DP写起来很简单，就是一个递推式。

具体地说，就是把询问、隔板按高度从小到大排序，依次作为节点插入树中，若当前询问的高度，大于等于当前隔板的高度，就合并相邻两列，建一个新节点，如此建出一棵树。而DP的时候就不用特别的去求前缀和了，直接递推过来就可以。

程序：

方法1：

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 using namespace std;

 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

 #define DWN(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i)

 #define mset(a, b) memset(a, b, sizeof(a))

 #define pb push_back

 const int maxn = 2e5+;

 int n, m;

 struct Node

 {

     int h, id;

     bool operator < (const Node &AI) const

     {

         return h == AI.h ? id < AI.id : h < AI.h;

     }

 }a[maxn];

 struct Query

 {

     int h, ty;

     Query(int h = , int ty = ):

         h(h), ty(ty) {}

     bool operator < (const Query &AI) const

     {

         return h == AI.h ? ty < AI.ty : h < AI.h;

     }

 };

 int fa[maxn*][], bel[maxn*], to[maxn][], tip[maxn*], bot[maxn*], t_cnt;

 int emp[maxn*], f[maxn*], d[maxn*];

 vector <Query> g[maxn*];

 template <class TAT>

 void Ckmax(TAT &a, const TAT &b)

 {

     if (a < b) a = b;

 }

 int Getbel(int x)

 {

     return x == bel[x] ? x : bel[x] = Getbel(bel[x]);

 }

 void prepare()

 {

     sort(a+, a+n);

     REP(i, , n) bel[i] = tip[i] = i, bot[i] = fa[i][] = fa[i][] =  to[i][] = to[i][] = , g[i].clear();

     t_cnt = n;

     REP(i, , n-)

     {

         int x = Getbel(a[i].id), y = Getbel(a[i].id+);

         t_cnt ++, g[t_cnt].clear();

         fa[tip[x]][] = fa[tip[y]][] = t_cnt;

         bot[t_cnt] = a[i].h;

         to[t_cnt][] = tip[x], to[t_cnt][] = tip[y];

         bel[x] = y;

         tip[y] = t_cnt;

     }

     bot[] = 0x3fffffff;

     REP(j, , )

         REP(i, , t_cnt)

             fa[i][j] = fa[fa[i][j-]][j-];//, printf("%d %d : %d\n", i, j, fa[i][j]);

 }

 void work()

 {

     mset(d, ), mset(f, );

     REP(i, , t_cnt)

     {

         if (!g[i].empty())

         {

             sort(g[i].begin(), g[i].end());

             int tmp, sum, sz = g[i].size(), j = , t_j;

             d[i] = sum = emp[i]+((i > n) ? f[to[i][]]+f[to[i][]] : );

             while (j < sz)

             {

                 tmp = g[i][j].ty ?  : -, t_j = j;

                 while (t_j+ < sz && g[i][t_j+].h == g[i][j].h)

                     t_j ++, tmp += (g[i][t_j].ty ?  : -);

                 sum += tmp;

                 Ckmax(d[i], sum);

                 j = t_j+;

             }

             f[i] = sum;

         }

         if (i > n)

         {

             Ckmax(d[i], emp[i]+d[to[i][]]+d[to[i][]]);

             Ckmax(f[i], f[to[i][]]+f[to[i][]]);

         }

 //        printf("%d %d\n", d[i], f[i]);

     }

 }

 int main()

 {

 //    freopen("a.in", "r", stdin);

 //    freopen("a.out", "w", stdout);

     int T, iCase = ;

     scanf("%d", &T);

     while (T --)

     {

         scanf("%d %d", &n, &m);

         REP(i, , n-) scanf("%d", &a[i].h), a[i].id = i;

         prepare();

         mset(emp, );

         REP(i, , m)

         {

             int x, h, ty;

             scanf("%d %d %d", &x, &h, &ty);

             DWN(j, , )

                 if (bot[fa[x][j]] <= h) x = fa[x][j];

             g[x].pb(Query(h, ty));

             emp[x] += (ty == );

         }

         work();

         printf("Case #%d: %d\n", ++iCase, d[t_cnt]);

     }

     return ;

 }

方法2：

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 using namespace std;

 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

 #define mset(a, b) memset(a, b, sizeof(a))

 #define max_(a, b) a > b ? a : b

 #define pb push_back

 const int maxn = 2e5+;

 int n, m;

 struct Node

 {

     int h, id;

     Node (int h = , int id = ):

         h(h), id(id) {}

     bool operator < (const Node &AI) const

     {

         return h == AI.h ? id < AI.id : h < AI.h;

     }

 }a[maxn];

 struct Query

 {

     int x, y, z;

     void read(){ scanf("%d %d %d", &x, &y, &z); }

     bool operator < (const Query &AI) const

     {

         return y == AI.y ? x < AI.x : y < AI.y;

     }

 }b[maxn];

 int f[maxn], g[maxn], dp[maxn*][];

 vector <int> e[maxn*];

 int find_fa(int x) { return f[x] == x ? x : f[x] = find_fa(f[x]); }

 void dfs(int x)

 {

     for (int i = , siz = e[x].size(); i < siz; ++i)

     {

         int y = e[x][i];

         dfs(y);

         dp[x][] += max_(dp[y][], dp[y][]);

         dp[x][] += dp[y][];

     }

 }

 int main()

 {

 //    freopen("a.in", "r", stdin);

 //    freopen("a.out", "w", stdout);

     int T, iCase = ;

     scanf("%d", &T);

     while (T --)

     {

         scanf("%d %d", &n, &m);

         REP(i, , n-) scanf("%d", &a[i].h), a[i].id = i;

         REP(i, , m) b[i].read();

         REP(i, , n)

         {

             f[i] = g[i] = i;

             e[i].clear(), dp[i][] = dp[i][] = ;

         }

         sort(a+, a+n), sort(b+, b+m+);

         int now = n, cnt_n = , cnt_m = ;

         while (cnt_m <= m || cnt_n < n)

         {

             if (cnt_m == m+ || cnt_n < n && a[cnt_n].h <= b[cnt_m].y)

             {

                 int x = find_fa(a[cnt_n].id), y = find_fa(a[cnt_n].id+);

                 e[++now].clear(), dp[now][] = dp[now][] = ;

                 e[now].pb(g[x]), e[now].pb(g[y]);

                 f[x] = y, g[y] = now;

                 cnt_n ++;

             }

             else

             {

                 int x = find_fa(b[cnt_m].x);

                 if (b[cnt_m-].y == b[cnt_m].y && find_fa(b[cnt_m-].x) == x)

                     dp[g[x]][b[cnt_m].z] ++;

                 else

                 {

                     e[++now].clear(), dp[now][] = dp[now][] = ;

                     e[now].pb(g[x]);

                     g[x] = now;

                     dp[now][b[cnt_m].z] ++;

                 }

                 cnt_m ++;

             }

         }

         dfs(now);

         printf("Case #%d: %d\n", ++iCase, max_(dp[now][], dp[now][]));

     }

     return ;

 }

巴特西

HDU 5575 Discover Water Tank 并查集树形DP

最新文章

热门文章

巴特西

HDU 5575 Discover Water Tank 并查集 树形DP

最新文章

热门文章

HDU 5575 Discover Water Tank 并查集树形DP