基站选址

首先我们需要一个暴力 dp，首先一个思路是设 $f_{i,j}$ 表示设置 $i$ 个基站，前 $j$ 个的代价，但是这样不好转移，主要问题是不知道 $j$ 是否会被后面的基站所覆盖 ，一个常见思路是我们可以强制第 $j$ 个放一个基站，这样就变得好转移了，因为我们相当于认为这个点一定被覆盖了，代价也就变得确定了。

当然为了计算出最后的答案，我们可以在最后加上一个村庄。

有了状态， dp 方程变得显然了。我们有：

$$
f_{i,j}=\min\limits_{0\le k<j}{ f_{i-1,k} +\sum\limits_{k\le l\le j,d_{l}+s_l<d_j,d_l-s_l>d_k}w_l }+c_j
$$

其中当 $i=1$ 的时候，注意到 $f_{i-1,k}$ 其实是没有什么意义的，设置为 $0$，而后面 $\sum$ 中的第三个限制也不复存在了。

我们用线段树来做，那么我们线段树中的就需要维护每个点的代价，如果一个区间，基站建在右端点右边，那么左端点再往左的区间，如果上一个基站建在这个区间中，那么就会有 $w$ 的代价，相当于区间加代价。

那么对于 $i=1$ 来说，其实是比较难处理的一个点，现在看来，把所有的 $f_{0,i}$ 设置为 $0$，然后每次全局覆盖是最优的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 110
#define M 20010
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
// #define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int f[N][M],d[M],c[M],s[M],w[M],k,n;

struct Node{
    int minn,len,sum,tag;
    inline Node(){}
    inline Node(int minn,int len,int sum,int tag) : minn(minn),len(len),sum(sum),tag(tag) {}
}p[M<<2];
#define ls(k) k<<1
#define rs(k) k<<1|1
struct SegmentTree{
    inline void PushUp(int k){
        p[k].sum=p[ls(k)].sum+p[rs(k)].sum;p[k].minn=min(p[ls(k)].minn,p[rs(k)].minn);
    }
    inline void A(int k,int x){
        p[k].sum+=x*p[k].len;p[k].tag+=x;p[k].minn+=x;
    }
    inline void PushDown(int k){
        if(p[k].tag){
            A(ls(k),p[k].tag);A(rs(k),p[k].tag);p[k].tag=0;
        }
    }
    inline void Add(int k,int l,int r,int z,int y,int x){
        if(z<=l&&r<=y){A(k,x);return;}int mid=(l+r)>>1;PushDown(k);
        if(z<=mid) Add(ls(k),l,mid,z,y,x);
        if(mid<y) Add(rs(k),mid+1,r,z,y,x);PushUp(k);
    }
    inline int GetMin(int k,int l,int r,int z,int y){
        if(z<=l&&r<=y) return p[k].minn;int mid=(l+r)>>1;PushDown(k);int ans=INF;
        if(z<=mid) ans=min(ans,GetMin(ls(k),l,mid,z,y));
        if(mid<y) ans=min(ans,GetMin(rs(k),mid+1,r,z,y));return ans;
    }
    inline void Build(int k,int l,int r,int id){
        p[k].len=r-l+1;p[k].sum=p[k].tag=0;p[k].minn=INF;
        if(l==r){
            if(id>l) p[k].minn=p[k].sum=INF;
            else p[k].minn=p[k].sum=f[id][l];return;
        }int mid=(l+r)>>1;
        Build(ls(k),l,mid,id);Build(rs(k),mid+1,r,id);PushUp(k);
    }
}st;

struct sq{
    int l,r,v;
    inline bool operator < (const sq &b)const{
        return r<=b.r;
    }
}sq[M];

signed main(){
    // freopen("my.in","r",stdin);freopen("my.out","w",stdout);
    read(n);read(k);rep(i,2,n) read(d[i]);rep(i,1,n) read(c[i]);rep(i,1,n) read(s[i]);rep(i,1,n) read(w[i]);
    rep(i,1,n) sq[i].l=max(0,d[i]-s[i]),sq[i].r=d[i]+s[i],sq[i].v=w[i];sort(sq+1,sq+n+1);
    int sum=0;rep(i,1,n) sum+=w[i];
    n++;d[n]=INF;c[n]=0;s[n]=0;w[n]=INF;k++;
    rep(i,1,k){
        st.Build(1,0,n,i-1);int id=0;
        rep(j,i,n){
            while(sq[id+1].r<d[j]&&id<n){
                id++;
                int rk=lower_bound(d+1,d+n+1,sq[id].l)-d;rk--;
                if(i!=1){
                    if(rk>=0) st.Add(1,0,n,0,rk,sq[id].v);
                }
                else{
                    st.Add(1,0,n,0,n,sq[id].v);
                } 
            }
            f[i][j]=st.GetMin(1,0,n,0,j-1)+c[j];
            // printf("f[%d][%d]=%d\n",i,j,f[i][j]);
        }
    }
    int ans=INF;
    rep(i,1,k) ans=min(ans,f[i][n]);
    printf("%d\n",ans);ans=min(ans,sum);
    return 0;
}

APIO2016烟火表演

首先考虑一个暴力 DP，设 $f_{i,j}$ 表示以 $i$ 为根的子树所有烟火都在 $j$ 时爆炸的代价，显然状态数就炸了，不过显而易见的是 $f_{i,j}$ 是一个下凸的函数，而且是一个一次分段函数。

接下来是这个题的精髓部分，我们怎么优化呢。首先我们需要一个数据结构来维护这个函数，因为有合并操作，所以我们采用左偏树来做合并，我们让这个下凸包的斜率是依次减 $1$ 的，要做到这一点只需要多次加入拐点，也就是说，如果一个拐点两边斜率相差 $2$，那么我们就插入两个拐点进去，对于每个点，我们只记录其横坐标，而不关心他们在 $y$ 方向的平移。

那么现在我们假设拿到了 $u$ 的函数，$u$ 的父亲是 $v$，之间连得边长度为 $l$，设 $L,R$ 为 $u$ 的函数中斜率为 $0$ 的函数的两个端点，那么我们显然有：

$$
\begin{cases}
f_v(x)=f_u(x)+l &(x\le L)\
f_v(x)=f_u(L)+l-(x-L)&(L<x\le L+l)\
f_v(x)=f_u(L)&(L+l<x\le R+l)\
f_v(x)=f_u(L)+(x-R)-l&(x>R+l)
\end{cases}
$$

所以我们要做的是把最右边一段斜率改为 $1$，做到这个只需要删除最大值直至只剩下一个最大值，这是因为斜率为 $0$ 的那一段右边只可能有一段。

接下来我们把斜率为 $0$ 的那段向右平移，只需要把最大值和次大值拿出来即可。

最后我们需要插入一段斜率为 $-1$ 的段，其实这个第二步我们已经实现了。

至于叶子，我们需要特殊判断。左偏树维护函数很好的题目。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 300010
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

struct Node{
    int ls,rs,v,dist;
    inline Node(){}
    inline Node(int ls,int rs,int v,int dist) : ls(ls),rs(rs),v(v),dist(dist) {}
}p[N*20];
struct edge{
    int to,next,w;
    inline void Init(int to_,int ne_,int w_){
        to=to_;next=ne_;w=w_;
    }
}li[N<<1];
int rt[N],head[N],tail;
inline void Add(int from,int to,int w){
    li[++tail].Init(to,head[from],w);head[from]=tail;
}
int tot=0;
inline int NewNode(int val){
    ++tot;p[tot]=Node(0,0,val,1);assert(tot<=N*20);
    return tot;
}
#define ls(k) p[k].ls
#define rs(k) p[k].rs
struct LeftHeap{
    inline int Merge(int a,int b){
        if(!a||!b) return a+b;if(p[b].v>p[a].v) swap(a,b);
        rs(a)=Merge(rs(a),b);if(p[rs(a)].dist>p[ls(a)].dist) swap(rs(a),ls(a));
        p[a].dist=p[rs(a)].dist+1;return a;
    }
    inline int Pop(int k){return Merge(ls(k),rs(k));}
    inline void dfs(int k){
        if(!k) return;
        printf("k=%d ls=%d rs=%d v=%d\n",k,ls(k),rs(k),p[k].v);dfs(ls(k));dfs(rs(k));
    }
    inline void Print(int k){
        dfs(k);
    }
}st;

int n,m;
ll sum[N];

inline void dfs(int k,int l){
    // printf("k=%d\n",k);
    int cnt=0;
    Next(k){
        cnt++;
        int to=li[x].to,w=li[x].w;dfs(to,w);
        sum[k]+=sum[to]+w;
    }
    Next(k){
        int to=li[x].to;
        rt[k]=st.Merge(rt[k],rt[to]);
    }
    // printf("k=%d rt[k]=%d\n",k,rt[k]);
    // printf("rt[3]=%d\n",rt[3]);
    if(k==1) return;
    if(!cnt){
        rep(i,1,2) rt[k]=st.Merge(rt[k],NewNode(l));
    }
    else{
        rep(i,1,cnt-1){
            rt[k]=st.Merge(ls(rt[k]),rs(rt[k]));
        }
        int a=p[rt[k]].v;rt[k]=st.Merge(ls(rt[k]),rs(rt[k]));
        int b=p[rt[k]].v;rt[k]=st.Merge(ls(rt[k]),rs(rt[k]));
        // printf("a=%d b=%d\n",a,b);
        a+=l;b+=l;rt[k]=st.Merge(rt[k],NewNode(a));rt[k]=st.Merge(rt[k],NewNode(b));
    }
}

P s[N];int top;

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);
    rep(i,2,n+m){
        int fat,w;read(fat);read(w);Add(fat,i,w);
    }
    dfs(1,0);
    // st.dfs(rt[1]);
    int maxx=p[rt[1]].v;int now=0;Next(1) now++;
    while(rt[1]){
        int maxx=p[rt[1]].v;
        while(p[rt[1]].v==maxx) rt[1]=st.Pop(rt[1]),now--;
        s[++top]=mp(maxx,now);
    }
    // rep(i,1,top) printf("%d %d\n",s[i].fi,s[i].se);
    int ans=sum[1];
    // printf("ans=%d\n",ans);
    int lst=0;
    dec(i,1,top){
        if(s[i].se>=0) break;
        int len=s[i].fi-lst;ans+=len*s[i].se;lst=s[i].fi;
    }
    printf("%lld\n",ans);
    return 0;
}

ARC070E NarrowRectangles

这个题实际上是烟火表演的弱化版，不过还是略有不同：

  • 首先，一样用堆来维护函数，不过因为不需要支持合并，所以普通的堆即可。
  • 因为最右边或最左边的斜率难以确定，我们这里采用用两个堆来维护一个函数的方法，即设 $L,R$ 为斜率为 $0$ 的一段的左右端点，我们 $L$ 左边维护一个大根堆，$R$ 右边维护一个小根堆，我们并不关心除堆顶之外的元素。利用上个题的技巧：加点加多次来让相邻点的斜率之差为 $1$，我们可以维护这个函数与绝对值函数的加法。
  • 以及，我们需要维护斜率为 $0$ 段的左右端点的平移，这个直接打标机即可，最左和最右两边可能会有一些段不合法，不过我们不去管他。
  • 在上个题中，我们是采用倒推的方法，所以左右边界要卡的很准。不过这个题，因为符合的函数只有绝对值函数，所以我们可以直接维护答案是多少。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N number
#define M number
using namespace std;

typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;

const int INF=0x3f3f3f3f;
const dd eps=1e-9;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int t1,t2;
priority_queue<int> ql;
priority_queue<int,vector<int>,greater<int> > qr;

int n,l,r,ans;

signed main(){
    // assert(freopen("my.in","r",stdin));
    // assert(freopen("my.out","w",stdout));
    read(n);read(l);read(r);
    ql.push(r);qr.push(r);
    int lst=r-l;
    rep(i,2,n){
        int l,r;read(l);read(r);
        int now=r-l;
        t1-=lst;t2+=now;
        int L=ql.top()+t1,R=qr.top()+t2;
        // printf("t1=%d t2=%d\n",t1,t2);
        // printf("L=%d R=%d r=%d\n",L,R,r);
        if(L<=r&&r<=R){
            ql.push(r-t1);qr.push(r-t2);
        }
        else if(r<L){
            int k=ql.top()+t1;ql.pop();qr.push(k-t2);ql.push(r-t1);ql.push(r-t1);
            ans+=(L-r);
        }
        else{
            int k=qr.top()+t2;qr.pop();ql.push(k-t1);qr.push(r-t2);qr.push(r-t2);
            ans+=(r-R);
        }
        lst=now;
    }
    printf("%lld\n",ans);
    return 0;
}