题解 [ABC353G] Merchant Takahashi

cjh20090318 · 2024-05-16 17:33:03 · 题解

没打这次比赛，赛后来看题发现相较于其他场的 G 较简单。

题意

有 N 个小镇和 M 次市场，从小镇 i 移动到小镇 j 需花费 C \times \vert i-j \vert 元。

每次交易依次举行，第 i 次交易在小镇 T_i 举行，可获得 P_i 元。

你需要从小镇 1 出发，选择参加一些交易活动，来获取最多的钱。过程中无需保证钱非负。

分析

贪心无从下手，考虑动态规划。

状态设计

设 f_i 表示结束点在小镇 i 可以获取到的最多钱数。

初始状态

转移方程

设某次交易在小镇 T 举行，可获得 P 元。

可以用线段树优化，将绝对值拆开。

对于 i < T 的点维护 f_i - C \times i 的最大值，对于 i > T 的点维护 f_i + C \times i 的最大值，然后分别处理即可。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
const LL infll=0x3f3f3f3f3f3f3f3fll;
using ci=const int;
int n,c,m;
struct SEG{//线段树。
    #define lson (rt<<1)
    #define rson (rt<<1|1)
    LL mx[MAXN<<2];
    void build(ci rt,ci l,ci r){
        if(l==r){mx[rt]=-infll;return;}//初始化为极小值。
        int mid=(l+r)>>1;
        build(lson,l,mid),build(rson,mid+1,r);
        mx[rt]=max(mx[lson],mx[rson]);
    }
    void update(ci rt,ci l,ci r,ci pos,const LL&val){
        if(l==r){mx[rt]=max(mx[rt],val);return;}//对于每次交易取最大值。
        int mid=(l+r)>>1;
        pos<=mid?update(lson,l,mid,pos,val):update(rson,mid+1,r,pos,val);
        mx[rt]=max(mx[lson],mx[rson]);
    }
    LL query(ci rt,ci l,ci r,ci L,ci R){
        if(L<=l && r<=R) return mx[rt];
        int mid=(l+r)>>1;
        LL ret=-infll;
        if(L<=mid) ret=max(ret,query(lson,l,mid,L,R));
        if(mid<R) ret=max(ret,query(rson,mid+1,r,L,R));
        return ret;
    }
};
SEG s1,s2;
int main(){
    scanf("%d%d%d",&n,&c,&m);
    s1.build(1,1,n),s2.build(1,1,n);
    s1.update(1,1,n,1,c),s2.update(1,1,n,1,-c);//s1 维护绝对值加的部分，s2 维护绝对值减的部分。
    int t;LL p;
    for(int i=1;i<=m;i++){
        scanf("%d%lld",&t,&p);
        LL s=max(s1.query(1,1,n,1,t)-(LL)c*t,s2.query(1,1,n,t,n)+(LL)c*t)+p;//左边和右边分别取最大值。
        s1.update(1,1,n,t,s+(LL)c*t),s2.update(1,1,n,t,s-(LL)c*t);//更新当前点最大值。
    }
    LL ans=0;
    for(int i=1;i<=n;i++) ans=max({ans,s1.query(1,1,n,i,i)-(LL)c*i,s2.query(1,1,n,i,i)+(LL)c*i});//把扣减的距离加回来，取答案最大值。
    printf("%lld\n",ans);
    return 0;
}