注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

BZOJ3672 [Noi2014]购票  

2014-09-12 11:06:49|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
填好久以前的坑……
Description
给n个节点的有根树,节点1是根,给出每个节点的父亲和到父亲的边权(距离)。
如果你在节点i,想到节点j(j是i的祖先,且满足i与j的距离不超过l[i]),需要付出p[i]*dist(i,j)+q[i]的代价。
现在对于每个节点2~n,要输出这个节点到根的最小代价。
n≤200000。
Solution
裸dp是显然的,dp[i]=min_{i能到j} (dp[j]+p[i]*dist(i,j)+q[i])。
把这个式子稍微改改就变成了dp[i]=p[i]*dist[i]+q[i] + min_{i能到j} (dp[j]-p[i]*dist[j]),其中dist[i]表示i到根的距离。

假设树是一条链,并且我们无视l[i](即所有的l都是+∞),式子变成了dp[i]=p[i]*dist[i]+q[i] + min_{j<i} (dp[j]-p[i]*dist[j])。
min里面的式子的意思就是:一堆点(dist[j],dp[j])放在坐标平面上,问f(x,y)=y-kx的最小值,其中k是与j无关的量。显然最优解只可能取在下凸壳上,而且已知下凸壳找最优解也可以二分。
现在需要动态维护一个下凸壳,需要支持每次在坐标平面内加一个点。注意横坐标dist[]相对点的加入次序是单调增的,所以用栈维护就好了。弹栈暴力弹就行,时间复杂度O(n log n)。

现在仍然考虑在链上的情况,但是有l[i]的限制。我们对链建线段树,在线段树上的每个节点维护所对应区间的下凸壳,查询时在线段树上每个区间查询即可。时间复杂度O(n log^2 n)。

再考虑树上,但是无l[i]限制的情况。如果对树dfs依次计算每个节点的dp值,就需要我们的数据结构除了支持动态加点以外,还要支持“回退”。注意每次对栈的修改可以做到O(1),这时弹栈不能暴力弹,而是二分出一个合适的位置,只替换一个元素。这样每一次历史变动都能记录下来,就可以进行回退了。时间复杂度O(n log n)。

如果是树上有l[i]限制,那么把上述两种方法套在一起就行了= =……dfs时线段树每个节点维护一个“可持久化凸包”结构……时间复杂度O(n log^2 n)。

其他的方法:
直接将链上的情况套到树上,需要上树剖,时间复杂度O(n log^3 n),但是由于常数小也能过。
用树的点分治,每次先递归计算重心到根,然后用这一段更新其余的点,时间复杂度O(n log^2 n)。

(我的代码很神奇……先开内存池居然比每次malloc还慢……只比开vector快了一点点……)
/**************************************************************
    Problem: 3672
    User: saffah
    Language: C++
    Result: Accepted
    Time:14964 ms
    Memory:330640 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <list>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
#define g(x, y, z) for(int x = (y); x < (z); ++x)
#define h(x, y, z) for(int x = (y); x >= (z); --x)
#define foreach(x, y) for(__typeof(y.begin()) x = y.begin(); x != y.end(); ++x)
typedef long long LL;
typedef std::pair<int, int> PII;
typedef long double real;
 
using std::vector;
using std::lower_bound;
 
struct point{
    real k; LL x, y;
    inline point(real _k = 0, LL _x = 0, LL _y = 0) :k(_k), x(_x), y(_y){}
};
inline bool operator <(point a, point b){
    return a.k < b.k;
}
 
//Persistent Convex Hull 233
struct PCH{
    int n;
    point *curr, *hist, *hiend;
    int *hn, *hend;
    inline PCH(int size){
        n = 0;
        curr = (point *) malloc(sizeof(point) * (size + 2));
        hiend = hist = (point *) malloc(sizeof(point) * (size + 2));
        hend = hn = (int *) malloc(sizeof(int) * (size + 2));
    }
    inline void push(point a){
        point *pos;
        if(n == 0){
            a.k = 0x8080808080808080LL;
            *(hiend++) = *curr; *(hend++) = 0;
            *curr = a; n = 1;
        }else{
            int l = 0, r = n - 1;
            while(l < r){
                int cans = (l + r) >> 1;
                a.k = (real) (a.y - curr[cans].y) / (a.x - curr[cans].x);
                if(cans == n - 1 || a < curr[cans + 1]) r = cans; else l = cans + 1;
            }
            a.k = (real) (a.y - curr[l].y) / (a.x - curr[l].x);
            pos = curr + (l + 1);
            *(hiend++) = *pos; *(hend++) = n;
            *pos = a; n = l + 2;
        }
    }
    inline void pop(){
        curr[n - 1] = *(--hiend);
        n = *(--hend);
    }
    inline LL query(LL k){
        point a = k;
        point *pos = lower_bound(curr, curr + n, a);
        if(pos != curr) --pos;
        return pos->y - pos->x * k;
    }
};
 
struct node{
    node *ls, *rs;
    int l, r, m;
    PCH *data;
    inline node(int ll, int rr) :l(ll), r(rr), m((ll + rr) >> 1){
        if(l == r){
            ls = rs = NULL;
            data = new PCH(1);
        }else{
            ls = new node(l, m); rs = new node(m + 1, r);
            data = new PCH(r - l + 1);
        }
    }
    inline void push(int x, point y){
        data->push(y);
        if(l != r){
            if(x <= m) ls->push(x, y);
            else rs->push(x, y);
        }
    }
    inline void pop(int x){
        data->pop();
        if(l != r){
            if(x <= m) ls->pop(x);
            else rs->pop(x);
        }
    }
    inline LL query(int ll, int rr, LL k){
        if(ll > rr) return 0x1f1f1f1f1f1f1f1fLL;
        if(l == ll && r == rr) return data->query(k);
        else if(rr <= m) return ls->query(ll, rr, k);
        else if(ll > m) return rs->query(ll, rr, k);
        else return std::min(ls->query(ll, m, k), rs->query(m + 1, rr, k));
    }
};
 
vector<int> sons[200086];
int fa[200086]; LL pd[200086], p[200086], q[200086], l[200086], dp[200086], ddp[200086];
 
node *root;
 
inline void dfs(int i, LL dist, int dep){
    ddp[dep] = (dist += pd[i]);
    int ll = lower_bound(ddp, ddp + dep, dist - l[i]) - ddp;
    dp[i] = root->query(ll, dep - 1, p[i]) + q[i] + p[i] * dist;
    root->push(dep, point(0, dist, dp[i]));
    foreach(son, sons[i]) dfs(*son, dist, dep + 1);
    root->pop(dep);
}
 
int main(){
    int n; scanf("%d%*d", &n);
    f(i, 2, n){
        scanf("%d%lld%lld%lld%lld", fa + i, pd + i, p + i, q + i, l + i);
        sons[fa[i]].push_back(i);
    }
    root = new node(0, n - 1);
    dp[0] = 0; ddp[0] = 0;
    root->push(0, point());
    foreach(son, sons[1]) dfs(*son, 0, 1);
    f(i, 2, n) printf("%lld\n", dp[i]);
    return 0;
}
  评论这张
 
阅读(892)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018