【CF115E】Linear Kingdom Races 题解（线段树优化DP）

前言：前辈讲课时设的状态还是有些繁琐，感觉题解设的状态更简洁。

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

题目大意：给定$n$条道路和$m$场比赛，每个道路修建需要$c_i$，每场比赛需要使用$[l_i,r_i]$内的道路，收益为$p_i$。问最大收益。$n,m\leq 200000$

先将所有的区间右端点从小到大排序。

设$f[i][j]$表示已经考虑前$i$条道路，最右边没有修的道路是$j$。现在考虑转移。

如果不修第$i$条道路，那么最右边的没有修的道路就变成$i$了。有这样的方程$f[i][i]=max(f[i][i],f[i-1][j]) (0\leq j\leq i-1)$

如果修第$i$条道路，那么以$i$为右端点的比赛都能获得收益。有$f[i][j]=f[i-1][j]+p(0\leq j\leq l_i-1)$。但是不要忘记修路的费用，即$f[i][j]=f[i-1][j]-cost[i](0\leq j\leq i-1)$。

这样的转移是$O(n^2)$的，还不够优秀。注意到只需要维护区间最大值和序列和，我们可以用线段树来维护，只用维护懒标记，区间加和区间最大值这三个操作即可。

至于以右端点进行关键字排序，可以开一个$vector$数组来存左端点和值。

时间复杂度$O(n\log n)$。

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m;

struct Node

{

    int first,second;

};

vector<Node> a[];

struct node

{

    int lazy,a,max;

}tree[];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void pushdown(int index)

{

    tree[index*].lazy+=tree[index].lazy;

    tree[index*+].lazy+=tree[index].lazy;

    tree[index*].max+=tree[index].lazy;

    tree[index*+].max+=tree[index].lazy;

    tree[index].lazy=;

}

inline void update(int index,int l,int r,int ql,int qr,int x)

{

    if (ql<=l&&r<=qr) {tree[index].lazy+=x;tree[index].max+=x;return;}

    if (tree[index].lazy) pushdown(index);

    int mid=(l+r)/;

    if (ql<=mid) update(index*,l,mid,ql,qr,x);

    if (qr>mid) update(index*+,mid+,r,ql,qr,x);

    tree[index].max=max(tree[index*].max,tree[index*+].max);

}

inline int query(int index,int l,int r,int ql,int qr)

{

    if (ql<=l&&r<=qr) return tree[index].max;

    if (tree[index].lazy) pushdown(index);

    int mid=(l+r)/,res=;

    if (ql<=mid) res=max(res,query(index*,l,mid,ql,qr));

    if (qr>mid) res=max(res,query(index*+,mid+,r,ql,qr));

    return res;

}

signed main()

{

    n=read(),m=read();

    for (int i=;i<=n;i++) tree[i].a=read();

    for (int i=;i<=m;i++)

    {

        int l=read(),r=read(),x=read();

        a[r].push_back((Node){l,x});

    }

    for (int i=;i<=n;i++)

    {

        //f[i][i]=max(f[i][i],f[i-1][j])

        update(,,n,i,i,query(,,n,,i-));

        //f[i][j]=f[i-1][j]+p-cost;

        for (int j=;j<a[i].size();j++) update(,,n,,a[i][j].first-,a[i][j].second);

        update(,,n,,i-,-tree[i].a);

    }

    printf("%lld",tree[].max);

    return ;

}

巴特西

【CF115E】Linear Kingdom Races 题解（线段树优化DP）

最新文章

热门文章