当前位置：首页 > news >正文

题解：P11630 [WC2025] 士兵

news 2026/5/12 19:14:27

更差的阅读体验

考虑一个很菜的 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;
}

题外话：