专栏文章

题解：P14439 [JOISC 2013] 考拉 / Koala

FFire_flys
P14439题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min3eltd
此快照首次捕获于
2025/12/01 19:55
3 个月前
此快照最后确认于
2025/12/01 19:55
3 个月前
查看原文
日本神题，真的牛逼，推出来的时候超级激动。
首先对于这个题，肯定是要用动态规划的，我们先设计出转移方程。
设 dpidp_i 表示到达第 ii 个导师家里并休息后，体力的最大值，由于要走到前理事长的家，且走到那里不会回复体力，所以我们可以把前理事长的家视作第 n+1n+1 个导师的家，然后回复的体力为 00；由于初始坐标也不一定在 00，所以我们还要把初始坐标也加进去，视作第 00 个导师的家，回复的体力也为 00。
那么对于这个暴力的转移方程，是很好想的。对于某个导师 ii，它的位置可以从前面的导师的位置的最大体力值转移过来，然后我们取最大值，即：
dpi=max⁡(dpi,dpj−⌈ti−tjd⌉×a+bi)\begin{aligned}dp_i=\max(dp_i,dp_j- \lceil \frac{t_i-t_j}{d} \rceil\times a +b_i ) \end{aligned}
上面的式子满足 0≤j<i0\le j<i，意思是，从前面那个导师走过来要消耗 dpj−⌈ti−tjd⌉×adp_j- \lceil \frac{t_i-t_j}{d} \rceil\times a 的体力，因为你要刚好走到那个位置所以你要向上取整。
但是这样转移是 O(n2)O(n^2) 的，考虑优化。
我们知道：
⌈x−yd⌉=⌊x−y+d−1d⌋\begin{aligned}\lceil \frac{x-y}{d} \rceil=\lfloor \frac{x-y+d-1}{d} \rfloor \end{aligned}
并且： ⌊x−y+d−1d⌋=⌊xd⌋−⌊yd⌋+(x mod d>y mod d)\begin{aligned}\lfloor \frac{x-y+d-1}{d} \rfloor=\lfloor \frac{x}{d} \rfloor-\lfloor \frac{y}{d} \rfloor+(x \bmod d>y\bmod d) \end{aligned}
所以上面那个转移式子的第二项就可以写成：
dpj−⌊tid⌋×a+⌊tjd⌋×a−(ti mod d>tj mod d)×a+bi\begin{aligned}dp_j- \lfloor \frac{t_i}{d} \rfloor\times a +\lfloor \frac{t_j}{d} \rfloor\times a-(t_i\bmod d>t_j\bmod d)\times a +b_i \end{aligned}
然后我们把跟 jj 有关的项拿出来放到前面，变成：
dpj+⌊tjd⌋×a−(ti mod d>tj mod d)×a−⌊tid⌋×a+bi\begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a-(t_i\bmod d>t_j\bmod d)\times a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i \end{aligned}
好的现在如果没有那个余数的限制，那么这个题就是一个非常基础的线段树优化的板子，只需要把前面的那一部分记下来然后放到线段树上后直接转移即可。
但是这个玩意有一个取模的限制，所以我们还得再讨论一下。
我们把那个余数的限制拆开，变成：
dpj+⌊tjd⌋×a−a−⌊tid⌋×a+bi,(ti mod d>tj mod d)\begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a-a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i,(t_i\bmod d >t_j\bmod d) \end{aligned}
dpj+⌊tjd⌋×a−⌊tid⌋×a+bi,(ti mod d≤tj mod d)\begin{aligned}dp_j +\lfloor \frac{t_j}{d} \rfloor\times a- \lfloor \frac{t_i}{d} \rfloor\times a +b_i,(t_i\bmod d \le t_j\bmod d) \end{aligned}
那么变成了这个形式后，我们发现转移跟余数有关，且每次转移要从前面余数比当前大的或比当前小的转移过来（当然也可能有从相等的情况转移过来）。
所以我们有了一个想法：按余数为下标来存。但是模数 dd 太大了怎么办？离散化呗，我们先把所有的余数预处理出来，然后把余数离散化，存的时候按照余数离散化后的大小来存。
到了这里，这道题就差不多做完了，只需套上一个线段树板子，然后对于每个 ii 去维护 dpi+⌊tid⌋×adp_i +\lfloor \frac{t_i}{d} \rfloor\times a 的值即可，转移的时候从前面的最大值转移过来。
还要注意一些细节，比如前面提到的，边界的第 00 个导师家和第 n+1n+1 个导师家别忘了也把余数给处理了。还有一点是初始化要赋一个极小值，这个答案好像最小能去到 −1018-10^{18}。
AC codeCPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,inf=-8e18;
int k,m,d,a,n,stx,enx;
int dp[N],t[N],b[N];//dp[i]表示到第i个导师家里歇息的最大体力值
//(x-y+d-1)/d=x/d-y/d+(x%d>y%d) 
int f[N]; 
struct BIT{
	int t[N<<2];//存距离取模的余数为r的dp最大值 
	inline void push_up(int x){
		t[x]=max(t[x*2],t[x*2+1]);
		return;
	}
	inline void build(int l,int r,int x){
		t[x]=inf;
		if(l==r)return;
		int mid=l+r>>1;
		build(l,mid,x*2);
		build(mid+1,r,x*2+1);
		return;
	}
	void update(int pos,int l,int r,int x,int k){
		if(l==r){
			t[x]=max(t[x],k);
			//if(k==0)cout<<"pos="<<pos<<" l="<<l<<" r="<<r<<" t[x]="<<t[x]<<" x="<<x<<"\n";
			return;
		}
		int mid=l+r>>1;
		if(pos<=mid)update(pos,l,mid,x*2,k);
		else update(pos,mid+1,r,x*2+1,k);
		push_up(x);
	}
	inline int ask(int L,int R,int l,int r,int x){
		//if(L==R&&R==3)cout<<"x="<<x<<" l="<<l<<" r="<<r<<"\n";
		if(L<=l&&r<=R)return t[x];
		int mid=l+r>>1,res=inf;
		if(L<=mid)res=max(res,ask(L,R,l,mid,x*2));
		if(R>mid)res=max(res,ask(L,R,mid+1,r,x*2+1));
		return res; 
	}
}tree; 
vector<int> g;
int r[N],mp[N];//表示第i个坐标对d取模的余数（离散化后）,mp映射原来余数 
//dp[i]=dp[j]-(t[i]-t[j]+d-1)/d*a+b[i] = dp[j]+a* (t[j]/d) -a *(t[i]%d>t[j]%d) -a*(t[i]/d)+b[i] 
void lisanhua(){
	r[0]=stx%d,r[n]=enx%d;
	g.push_back(r[0]);g.push_back(r[n]);
	sort(g.begin(),g.end());
	g.erase(unique(g.begin(),g.end()),g.end());
	for(int i=0;i<=n;i++){
		int rr=r[i];
		r[i]=lower_bound(g.begin(),g.end(),r[i])-g.begin()+1;
		mp[r[i]]=rr;
	}
	return;
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>stx>>enx>>d>>a>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>b[i],dp[i]=inf;
		r[i]=t[i]%d;
		g.push_back(r[i]);
	}
	t[0]=stx;b[0]=0;
	n++;t[n]=enx;b[n]=0;
	lisanhua();dp[0]=0;
	int maxn=n+5;
	tree.build(1,maxn,1);
	//cout<<"maxn="<<maxn<<"\n";
	//cout<<"r[0]="<<r[0]<<"\n";
	tree.update(r[0],1,maxn,1,a*(t[0]/d));
	for(int i=1;i<=n;i++){
		int res1=tree.ask(1,r[i],1,maxn,1);//余数小于t[i]%d的部分 
		int res2=tree.ask(r[i],maxn,1,maxn,1);//余数大于等于它的部分 
		dp[i]=max(res1-a*(t[i]/d)-a+b[i],res2-a*(t[i]/d)+b[i]);
		tree.update(r[i],1,maxn,1,dp[i]+a*(t[i]/d));//修改 
	//	cout<<"res1="<<res1<<" res2="<<res2<<" dp["<<i<<"]="<<dp[i]<<" r["<<i<<"]="<<r[i]<<"\n";
	}
	cout<<dp[n]<<"\n";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...