题解：P11630 [WC2025] 士兵

· · 题解

更好的阅读体验

考虑一个很菜的 dp。假设 f_{i, j} 表示前 i 个人，对着 i 砍了 j 刀的方案数。那么很显然有转移：

f_{i, j} = \max_{k} \{f_{i-1, k} - m \times \max(0, j-k)\} + [j \ge a_i] \times b_i

然后我们注意到如果我们想要让 a_i 扣到 0，那么我们不需要太多多余的操作，因为假设 a_{i-1} 的操作次数 > a_i，我们让 a_i 的次数比 a_{i-1} 小是不消耗代价的；如果 a_{i-1} 的操作次数 t\le a_i，那么假设 a_i 的操作次数是 t'，那么代价就是 t' - t，显然当 t' = a_i 时 t' 取最小，因此在当前位置上的代价最小。所以这种情况下我们直接让 a_i 的操作次数 = a_i。

如果我们不想要让 a_i 扣到 0，那么也是同样道理的，把操作次数减的太小会让后面用更多的代价把操作次数加回去。因此这种情况下，我们让 a_i 的操作次数为 a_i - 1。

所以我们把上面那个转移方程的 \max 和艾弗森括号扔掉，只考虑下面三个转移：

f_{i, a_i} \leftarrow \max _{j < a_i} \{f_{i-1, j} - m \times (a_i - j)\} f_{i, a_i - 1} \leftarrow \max_{j \ge a_i}\{f_{i-1, j}\} f_{i, j} \leftarrow f_{i, j} + [j \ge a_i]b_i

第二个和第三个转移是简单的，一个是区间 \max，一个是区间加法，都可以用一棵线段树来维护。

第一个可以这样变换以下：

\max _{j < a_i} \{f_{i-1, j} - m \times (a_i - j)\} = \max_{j < a_i}\{f_{i-1, j} + m \times j\} - m \times a_i

所以我们再维护一个 f_{i, j} + m \times j 就可以了。

具体地，我们开两棵线段树，分别维护 f_{i, j} 和 f_{i, j} + m \times j，支持区间查询 \max，单点修改和区间加法。那么这道题就做完了，复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1000006
using namespace std;
int T,n,m,bn,a[N],a_[N],a1_[N],b[N],c[N];
struct Segtree {
    int tag[N<<2],tree[N<<2];
    void addtag(int p,int x){tag[p]+=x,tree[p]+=x;}
    void push_down(int p){addtag(p<<1,tag[p]),addtag(p<<1|1,tag[p]),tag[p]=0;}
    void build(int p,int l,int r)
    {
        tag[p]=0,tree[p]=-1e15;if(l==r)return;
        int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    void assign(int p,int l,int r,int k,int x)
    {
        if(l==r)return tree[p]=x,(void)0;
        push_down(p);int mid=l+r>>1;
        k<=mid?assign(p<<1,l,mid,k,x):assign(p<<1|1,mid+1,r,k,x);
        tree[p]=max(tree[p<<1],tree[p<<1|1]);
    }
    void update(int p,int l,int r,int L,int R,int x)
    {
        if(L<=l&&r<=R)return addtag(p,x);
        push_down(p);int mid=l+r>>1;
        if(L<=mid)update(p<<1,l,mid,L,R,x);
        if(R>mid)update(p<<1|1,mid+1,r,L,R,x);
        tree[p]=max(tree[p<<1],tree[p<<1|1]);
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return tree[p];
        push_down(p);int mid=l+r>>1,ret=-1e15;
        if(L<=mid)ret=max(ret,query(p<<1,l,mid,L,R));
        if(R>mid)ret=max(ret,query(p<<1|1,mid+1,r,L,R));
        return ret;
    }
}T1,T2;
void solve()
{
    scanf("%lld%lld",&n,&m),c[bn=1]=0;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]),c[++bn]=a[i],c[++bn]=a[i]-1;
    sort(c+1,c+1+bn),bn=unique(c+1,c+1+bn)-c-1;
    for(int i=1;i<=n;i++)
        a_[i]=lower_bound(c+1,c+1+bn,a[i])-c;
    for(int i=1;i<=n;i++)
        a1_[i]=lower_bound(c+1,c+1+bn,a[i]-1)-c;
    int _0=lower_bound(c+1,c+1+bn,0)-c;
    T1.build(1,1,bn),T2.build(1,1,bn);
    T1.assign(1,1,bn,_0,0),T2.assign(1,1,bn,_0,0);
    for(int i=1;i<=n;i++)
    {
        int fai_1=max(T1.query(1,1,bn,a1_[i],a1_[i]),T1.query(1,1,bn,a_[i],bn));
        int fai=max(T1.query(1,1,bn,a_[i],a_[i]),T2.query(1,1,bn,1,a1_[i])-m*a[i]);
        T1.assign(1,1,bn,a_[i],fai),T2.assign(1,1,bn,a_[i],fai+m*c[a_[i]]);
        T1.assign(1,1,bn,a1_[i],fai_1),T2.assign(1,1,bn,a1_[i],fai_1+m*c[a1_[i]]);
        T1.update(1,1,bn,a_[i],bn,b[i]),T2.update(1,1,bn,a_[i],bn,b[i]);
    }
    printf("%lld\n",T1.tree[1]);
}
main()
{
    scanf("%lld",&T);
    while(T--)solve();
    return 0;
}

题外话：

场上我使用 ABC 的开题顺序，并且获得了压线铜牌。