自动搬运

查看原文

来自洛谷，原作者为

	Ch1F4N HN 初三最菜 OIer|| 新的赛季 rp ++

搬运于2025-08-24 23:07:49，当前版本为作者最后更新于2025-06-06 10:47:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

你思考下我们到底在干嘛。

我们希望尽快走到终点，并且为了避免惩罚，需要在中途一些形如 $k \times p$ 的时刻踩在关键点上。

并且对于一个关键点，假若用其规避了 $k \times p$ 时刻的惩罚，就没必要用其规避 $(k+1) \times p$ 时刻的惩罚，因为对规避后面的惩罚无收益还浪费时间。

所以实际上我们只关心哪些关键点作为了规避惩罚的点，于是有一个 $O(n^2)$ 的 dp。

这个 dp 最难处理的项是 $i$ 转移到 $j$ 时有一个 $a_j-a_i$ 除以 $p$ 上取整，讨论 $a_j \bmod p,a_i \bmod p$ 的大小关系后可以拆成 $a_j/p$ 下取整，$a_i/p$ 下取整之差并且可能需要再加上 $1$，动态开点线段树维护 $a_k \bmod p = i$ 的最优决策即可做到 $O(n \log p)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define lowbit(x) (x&(-x))
const int maxn = 1e5+114;
int a[maxn],n,b,p,d;
int dp[maxn];
int tr[maxn*60],ls[maxn*60],rs[maxn*60],tot;
int root;
void upd(int &cur,int lt,int rt,int pos,int v){
	if(cur==0){
		cur=++tot;
		tr[cur]=1e18;
	}
	tr[cur]=min(tr[cur],v);
	if(lt==rt) return ;
	int mid=(lt+rt)>>1;
	if(pos<=mid) upd(ls[cur],lt,mid,pos,v);
	else upd(rs[cur],mid+1,rt,pos,v);
}
int ask(int cur,int lt,int rt,int l,int r){
	if(cur==0) return 1e18;
	if(r<lt||rt<l) return 1e18;
	if(l<=lt&&rt<=r) return tr[cur];
	int mid=(lt+rt)>>1;
	return min(ask(ls[cur],lt,mid,l,r),ask(rs[cur],mid+1,rt,l,r));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>b>>p>>d>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=0;i<=n;i++) dp[i]=1e18;
	dp[0]=0;
	upd(root,0,p-1,0,dp[0]);
	int ans=b+(b-1)/p*d;
	for(int i=1;i<=n;i++){
		dp[i]=min(dp[i],ask(root,0,p-1,0,p-1)+(a[i]/p+1)*(p+d));
		dp[i]=min(dp[i],ask(root,0,p-1,a[i]%p,p-1)+a[i]/p*(p+d));
		dp[i]-=d;
		upd(root,0,p-1,a[i]%p,dp[i]-(a[i]/p)*(p+d));
		int dist=(b-a[i]);
		ans=min(ans,dp[i]+dist+(dist-1)/p*d);
	}
	cout<<ans<<"\n";
	return 0;
}