专栏文章

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

lliangjiande
P14439题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min38lwx
此快照首次捕获于
2025/12/01 19:50
3 个月前
此快照最后确认于
2025/12/01 19:50
3 个月前
查看原文

闲话

又被大手子拉过来做题了，他说做了三个小时，一定要让我尝尝。。。

正文

式子一

题意比较显然，所以我们可以很快地推出一个初始的转移方程，其中 dpidp_i 表示在位置 ii 得到的最大体力值。
dpi=max⁡(dpi,dpj+Bi−A),j∈[max⁡(0,i−D),i−1]dp_i= \max (dp_i,dp_j+B_i-A),j\in[ \max (0,i-D),i-1]
这个转移方程很简单，但是美中不足的是，它与位置大小相关，这意味着使用单调队列优化上述式子，依旧是 Θ(M)\Theta(M) 的时间复杂度，这明显不行。

式子二

所以我们考虑换一种式子，其中 dpidp_i 表示在第 ii 个关键点（起点为 00，终点为 n+1n+1，导师家）时的最大体力值。 dpi=max⁡(dpj−A×⌈ti−tjD⌉)+Bi,j∈[0,i−1]dp_i= \max (dp_j-A\times \left \lceil \frac{t_i-t_j}{D} \right \rceil )+B_i,j\in[0,i-1]
这个式子也比较好推，但是它的相关变量（tit_i，tjt_j，dpidp_i，dpjdp_j）都混在一起了，我们没办法快速维护只与 jj 相关的变量。
难道我们只能每次遍历然后暴力转移吗？

式子三

显然不是。
考虑把向上取整的部分拆掉，把与 ii 相关的部分拆出括号。
我们想到一种常见的定义：
⌈a−bd⌉=(x−y)+[ra>rb],ra∈[0,d−1],rb∈[0,d−1]\left \lceil \frac{a-b}{d} \right \rceil=(x-y)+[r_a>r_b],r_a\in[0,d-1],r_b\in[0,d-1] 其中 x=⌊ad⌋x=\left \lfloor \frac{a}{d} \right \rfloor，y=⌊bd⌋y=\left \lfloor \frac{b}{d} \right \rfloor，ra≡x mod dr_a\equiv x\bmod d，rb≡y mod dr_b\equiv y\bmod d，方括号为艾弗森括号。
这个式子我们带入回式子二中，就会得到： dpi=max⁡(dpj+A×qj−A×[ri>rj])+Bi−A×qidp_i= \max (dp_j+A\times q_j-A\times [r_i>r_j])+B_i-A\times q_i 其中 qiq_i 与上述 xx 相同含义，qjq_j 与上述 yy 相同含义。

式子四

这个艾弗森括号很恶心啊，它保留了最后一个与 ii 相关的变量，我们考虑把它也拆掉。
惊奇地发现，这个括号只是一个幌子，我们只要分类讨论，分成余数的大小比较就可以了。
所以最后的式子就出来了： dpi=max⁡(dpj+A×qj,dpk+A×qk−A)+Bi−A×qi,qj∈[ri,D−1],qk∈[0,ri−1]dp_i= \max (dp_j+A\times q_j,dp_k+A\times q_k-A)+B_i-A\times q_i,q_j\in[r_i,D-1],q_k\in[0,r_i-1]

最终实现

我们费尽千辛万苦最终推出来的式子终于把所有的 ii 从递推中摘了出来，但是看着上面的依托，我们到底要怎么优化呢？
我们发现每次都要在前面找两遍最大值，还要更新当前位置的最大值以便后续更新。
所以我们需要一种可以支持区间查询最大值，单点修改为最大值的数据结构，这明显就是线段树。
那么线段树是依据什么建立的？
我们发现，式子四的两个变量的取值只和它们的余数大小相关，所以我们把距离对 DD 的余数作为下标建立线段树就可以成功转移了。
还有一点，DD 和 tit_i 的值域太大了，线段树存不下，这里可以采用动态开点或把余数离散化两种技巧，我选择了后者。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=6e18+10,N=1e6+10;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((a[x].l+a[x].r)>>1)
struct node{
	int l,r,maxn;
}a[N<<2];
void push_up(int x){
	a[x].maxn=max(a[ls(x)].maxn,a[rs(x)].maxn);
}
void build(int x,int l,int r){
	a[x].l=l;a[x].r=r;a[x].maxn=-INF;
	if(l==r) return;
	build(ls(x),l,mid);build(rs(x),mid+1,r);
}
void update(int x,int pos,int w){
	if(a[x].l==a[x].r){
		a[x].maxn=max(a[x].maxn,w);
		return;
	}
	if(pos<=mid) update(ls(x),pos,w);
	else update(rs(x),pos,w);
	push_up(x);
}
int query(int x,int L,int R){
	if(L>R) return -INF;
	if(a[x].l>=L&&a[x].r<=R) return a[x].maxn;
	if(R<=mid) return query(ls(x),L,R);
	else if(L>mid) return query(rs(x),L,R);
	return max(query(ls(x),L,R),query(rs(x),L,R));
}
#undef ls
#undef rs
#undef mid
int t[N],b[N],dp[N];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int K,M,d,A,n;cin>>K>>M>>d>>A>>n;
	V<int>lsh;
	lsh.pb(K%d);
	FOR(i,1,n) cin>>t[i]>>b[i],lsh.pb(t[i]%d);
	lsh.pb(M%d);
	sort(lsh.begin(),lsh.end());
	lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
	int siz=lsh.size();
	build(1,0,siz-1);
	int fir=lower_bound(lsh.begin(),lsh.end(),K%d)-lsh.begin();
	update(1,fir,A*(int)(K/d));
	dp[0]=0;
	t[n+1]=M,b[n+1]=0;
	FOR(i,1,n+1){
		int qi=t[i]/d,mod=lower_bound(lsh.begin(),lsh.end(),t[i]%d)-lsh.begin();
		int lef=query(1,0,mod-1);
		int rig=query(1,mod,siz-1);
		int lls=-INF;
		if(lef>-INF/2) lls=max(lls,lef-A);
		if(rig>-INF/2) lls=max(lls,rig);
		if(lls>-INF/2) dp[i]=lls-A*qi+b[i];
		else dp[i]=-INF;
		if(dp[i]>-INF/2) update(1,mod,dp[i]+qi*A);
	}
	cout<<dp[n+1];
	return 0;
}

评论

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

正在加载评论...