关闭

[堆与斜率] BZOJ 4585: [Apio2016]烟火表演

228人阅读 评论(0) 收藏 举报
分类:

Solution

H(x)=|xwu|
这是一个凸包。并且在相近的两个点对(可以有重复)斜率相差1
考虑如何从子树加入一条连向父亲的边,形成新的凸包H
设取到最小值的区间为[L,R]
H(x)=H(x)+wH(L)+w(xL)H(L)H(L)+(xR)wxLLxL+wL+wxR+wR+wx

这其实是把L左边的一部分平移,加入1,0,1三个斜率。
这里的方法可以维护这个东西,这道题因为要合并不同子树的拐点,所以就用可并堆啦~

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 606060;

inline char get(void) {
    static char buf[100000], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, 100000, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
template<typename T>
inline void read(T &x) {
    static char c; x = 0; int sgn = 0;
    for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
    for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}

struct node {
    node *l, *r;
    ll v;
    node(ll _v = 0): v(_v), l(NULL), r(NULL) {}
};
node mem[N];
node *rt[N];
int n, m, mnt, pnt;
ll sum;
int fa[N], w[N], deg[N];

inline int Rand(void) {
    static int x = 31253125;
    x += (x << 4) + 1;
    return x & 65536;
}
inline node *Merge(node *x, node *y) {
    if (!x || !y) return x ? x : y;
    if (x->v < y->v) swap(x, y);
    if (Rand()) x->l = Merge(x->l, y);
    else x->r = Merge(x->r, y);
    return x;
}
inline void Pop(node *&x) {
    x = Merge(x->l, x->r);
}

int main(void) {
    freopen("1.in", "r", stdin);
    read(n); read(m);
    for (int i = 2; i <= n + m; i++) {
        read(fa[i]); read(w[i]);
        sum += w[i]; ++deg[fa[i]];
    }
    for (int i = n + m; i > 1; i--) {
        ll l = 0, r = 0;
        if (i <= n) {
            while (--deg[i]) Pop(rt[i]);
            r = rt[i]->v; Pop(rt[i]);
            l = rt[i]->v; Pop(rt[i]);
        }
        mem[++mnt] = node(l + w[i]);
        mem[++mnt] = node(r + w[i]);
        rt[i] = Merge(rt[i], mem + mnt - 1);
        rt[i] = Merge(rt[i], mem + mnt);
        rt[fa[i]] = Merge(rt[fa[i]], rt[i]);
    }
    while (deg[1]--) Pop(rt[1]);
    while (rt[1]) {
        sum -= rt[1]->v; Pop(rt[1]);
    }
    printf("%lld\n", sum);
    return 0;
}
2
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

BZOJ4585: [Apio2016]烟火表演

Description 烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安 全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成 一...
  • wxh010910
  • wxh010910
  • 2017-02-19 19:13
  • 573

BZOJ4585 [Apio2016]烟火表演

“这个凸包的形式,妙啊,他妙啊,妙啊” 王梦迪神犇在讲题的时候写的题解挺详细的 我们对每个点,有一个把子树内长度统一的花费关于统一成的长度的函数f(x),易知这个函数是下凸的,对于一个点x,设他的儿子...
  • neither_nor
  • neither_nor
  • 2016-06-20 13:12
  • 1232

BZOJ 4585 [Apio2016]烟火表演 可并堆

#include #include #include #define N 300005 using namespace std; typedef long long LL; struct Nod...
  • YihAN_Z
  • YihAN_Z
  • 2017-06-29 11:18
  • 145

[DP 可并堆维护凸包优化] BZOJ 4585 [Apio2016]烟火表演

垂死梦中惊坐起,膜拜神犇王梦迪 #include #include #include using namespace std; typedef long lo...
  • u014609452
  • u014609452
  • 2016-08-28 18:42
  • 745

【BZOJ4518】征途,斜率优化DP

真理是上帝手中破裂的镜子,每个人手里都拿了一块。
  • xym_CSDN
  • xym_CSDN
  • 2016-04-11 21:25
  • 1652

[BZOJ1010][HNOI2008]玩具装箱toy 斜率优化第一题

很明显我们得到朴素的转移方程dp[i]=min{dp[j]+(i−j−1+sum[i]−sum[j]−L)2,dp[i]}  (0≤j<i)dp[i]=min\{dp[j]+(i-j-1+sum[i]...
  • slongle_amazing
  • slongle_amazing
  • 2015-12-16 17:13
  • 1682

BZOJ 4174 tty的求助 莫比乌斯反演

题目大意:求∑Nn=1∑Mm=1∑m−1k=0⌊nk+xm⌋ mod 998244353\sum_{n=1}^N\sum_{m=1}^M\sum_{k=0}^{m-1}\lfloor\frac{nk+...
  • PoPoQQQ
  • PoPoQQQ
  • 2015-07-09 19:13
  • 2635

[DP 可并堆维护凸包优化] BZOJ 4585 [Apio2016]烟火表演

垂死梦中惊坐起,膜拜神犇王梦迪 #include #include #include using namespace std; typedef long lo...
  • u014609452
  • u014609452
  • 2016-08-28 18:42
  • 745

BZOJ 4585 [Apio2016]烟火表演 可并堆

#include #include #include #define N 300005 using namespace std; typedef long long LL; struct Nod...
  • YihAN_Z
  • YihAN_Z
  • 2017-06-29 11:18
  • 145

【动态规划17】bzoj3675 [Apio2014]序列分割(斜率优化)

斜率优化 瞎搞一搞
  • Flanoc
  • Flanoc
  • 2017-06-18 20:51
  • 294
    个人资料
    • 访问:30010次
    • 积分:2295
    • 等级:
    • 排名:第19090名
    • 原创:185篇
    • 转载:0篇
    • 译文:0篇
    • 评论:0条
    友情链接