P11491 [BalticOI 2023] Tycho-题解

怎么题解区都觉得简单？畏惧了。

简要题意

你从数轴上的 $0$ 点出发，要到 $b$ 点。

每秒你可以：

• 前进一步（坐标 $+1$）
• 原地等待（坐标不变）

对于每个非负整数 $k$，在第 $k \times p$ 秒末（即 $0, p, 2p, 3p, \dots$ 秒末），如果你的坐标不是 $0$、$b$、以及给定的 $a_1,a_2,\dots,a_n$ 中的任何一个，那么就会产生 $d$ 的代价。每秒会产生 $1$ 的代价。

最小化总代价。

题目分析

转化题意

考虑转移，注意到疯狂的数据范围，肯定不能设计与距离或时间有关的状态，考虑为什么要给你数组 $a$？

不妨设计与安全点有关的状态。定义 $dp_i$ 为走到第 $i$ 个安全点的最小代价，但你发现后面的转移也要扯到走到这里的时间，也就是要枚举，显然不可接受。

如何减少分子上第二项代价，考虑我们要在一些安全坐标上停留到 $k \times p$ 秒，其中 $k$ 是非负整数，然后再往后走，这样能尽可能减少代价。

在这个基础上，我们可以对这个状态作补充：第 $i$ 个安全点等到 $k \times p$ 秒的最小代价是多少。

这样有什么好处？发现大代价是周期来的，这样做就只用考虑两点之间的距离，这中间的大代价次数也是可计算的，避免了对时间的胡乱考虑。

转移方程

考虑从 $j$ 号安全点到 $i$ 号安全点，那么：

$$dp_i = \min_j \left\{ dp_j + \left\lceil \frac{a_i - a_j}{p} \right\rceil \cdot p + \left\lfloor \frac{a_i - a_j - 1}{p} \right\rfloor \cdot d \right\}$$

其中第二项是补全到 $p$ 的倍数，保持状态的一致；第三项是计算两点间的大代价次数。

考虑这个转移的意义：

• 选出一部分安全点，在这些点上，时间被对齐到 $k \times p$。
• 而两个选出来的点之间的那些时刻，如果落在不安全位置，大代价直接算入这段转移代价里。

到这里可以设计一个平方的算法，可以通过子任务 4。

进一步优化

你发现这式子很不可做，上下取整怎么搞？

我们考虑对安全点的坐标按模 $p$ 分类，把坐标写成 $a_i=q_i p+r_i$ 的形式，那么对于原始转移中的 $a_i-a_j$ 项，就可以写成 $(q_i-q_j)p+(r_i-r_j)$ 的形式。

对于 $(q_i-q_j)p+(r_i-r_j)$ 这个东西除 $p$ 的取整就要考虑 $(r_i-r_j)$ 的正负：

当 $r_j<r_i$ 时

这时 $\dfrac{r_i-r_j}{p}$ 是一个在 $(0,1)$ 之间的小数，所以：

$$\left\lceil\frac{a_i-a_j}{p}\right\rceil=q_i-q_j+1$$

而：

$$\left\lfloor\frac{a_i-a_j-1}{p}\right\rfloor=q_i-q_j$$

代回去：

$$dp_i = \min\left\{ dp_j+(q_i-q_j+1)p+(q_i-q_j)d \right\}$$

也就是：

$$dp_i = \min\left\{ dp_j-q_j p-q_j d \right\} +q_i p+q_i d+p$$

当 $r_j\ge r_i$ 时

这时不用多补一个 $p$，所以：

$$\left\lceil\frac{a_i-a_j}{p}\right\rceil=q_i-q_j$$

第二项也就是：

$$\left\lfloor\frac{a_i-a_j-1}{p}\right\rfloor=q_i-q_j-1$$

代回去：

$$dp_i = \min\left\{ dp_j+(q_i-q_j)p+(q_i-q_j-1)d \right\}$$

化一下：

$$dp_i = \min\left\{ dp_j-q_j p-q_j d \right\} +q_i p+q_i d-d$$

---

和 $i$ 相关的东西是不一样的，动不了。我们考虑把和 $j$ 相关的东西提出来：

$$G(j)=dp_j-q_jp-q_jd$$

于是转移就变成了非常自然的两类：

• 若 $r_j<r_i$：

$$dp_i=q_ip+q_id+\min_{r_j<r_i}G(j)+p$$

• 若 $r_j\ge r_i$：

$$dp_i=q_ip+q_id+\min_{r_j\ge r_i}G(j)-d$$

数据结构

现在只剩一个问题：怎么快速求出 $\min_{r_j<r_i}G(j)$ 和 $\min_{r_j\ge r_i}G(j)$。

你发现这个东西类似单点修，区间查问题。

注意 $r_j$ 只和 $a_j\bmod p$ 有关，因此我们可以对余数建一棵线段树，在余数 $r$ 的位置维护，所有已经处理过的点中，满足 $a_j\bmod p=r$ 的最小 $G(j)$。

于是：

• 对前面的第一种转移，查询区间 $[0,r_i-1]$，得到 $r_j<r_i$ 的最优前驱。
• 对前面的第二种转移，查询区间 $[r_i,p-1]$，得到 $r_j\ge r_i$ 的最优前驱。
• 算出 $dp_i$ 后，再用 $G(i)$ 更新余数 $r_i$ 的位置。

由于余数的范围很大，要使用动态开点线段树。

答案计算

上面的 $dp_i$ 定义要求，到达 $a_i$ 后，还要把时间补到某个 $p$ 的倍数。

但最后到达终点 $b$ 时，不需要再补到 $p$ 的倍数。所以最后从某个安全点 $a_i$ 直接走到终点 $b$ 的代价是：

• 时间代价：$b-a_i$。
• 中间额外代价次数：$\left\lfloor \dfrac{b-a_i-1}{p}\right\rfloor$。

答案就是下面这个式子：

$$\min_i\left\{ dp_i+(b-a_i)+\left\lfloor\frac{b-a_i-1}{p}\right\rfloor d \right\}$$

值得注意的是，起点，也就是 $i=0$ 也是安全点，要注意循环的起点。

代码实现

记得开 long long。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define db double
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
const int MX = 9e18;
const int N = 1e5 + 5;
int a[N];
int val[N];
int dp[N];
int root;
struct node 
{
    int mn;
    int ls,rs;
} tr[N*80];

int cnt = 0;

void update(int &c, int x, int k, int l, int r) {
    if (!c) 
    {
        c = ++cnt; 
        auto &t = tr[c];
        t.mn = MX;
    } 
    auto &t = tr[c];
    t.mn = min(t.mn, k);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x <= mid) update(t.ls, x, k, l, mid);
    else update(t.rs, x, k, mid + 1, r);
}

ll query(int c, int L, int R, int l, int r) 
{
    if (!c) return MX;
    auto &t = tr[c];
    if (l > R || r < L) return MX;
    if (L <= l && r <= R) return t.mn;
    int mid = (l + r) / 2;
    return min(query(t.ls, L, R, l, mid), query(t.rs, L, R, mid + 1, r));
}

int b, p, d, n;

int G(int x)
{
    return dp[x] - val[x] - (a[x] / p) * d;
}

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];
        val[i] = a[i] - a[i] % p;
    }

    root = 0;
    dp[0] = 0;
    a[0] = 0;
    val[0] = 0;

    update(root, 0, G(0), 0, p - 1);

    for (int i = 1; i <= n; i++)
    {
        dp[i] = MX;
        int h = val[i] + (a[i] / p) * d;
        int r = a[i] % p;

        // r_j < r_i
        dp[i] = min(dp[i], h + query(root, 0, r - 1, 0, p - 1) + p);

        // r_j >= r_i
        dp[i] = min(dp[i], h + query(root, r, p - 1, 0, p - 1) - d);

        update(root, r, G(i), 0, p - 1);
    }

    int ans = MX;
    for (int i = 0; i <= n; i++)
    {
        ans = min(ans, dp[i] + b - a[i] + (b - a[i] - 1) / p * d);
    }
    cout << ans << endl;

    return 0;
}

简单题。

容易发现我们一定是走到一个地方然后等到 $p$ 的倍数秒，然后继续走到下一个位置，那么由此可以设计状态 $f_i$ 表示到 $i$ 个点等到 $p$ 的倍数秒的最小代价是多少，转移是

$$f_i=f_j+\lceil \dfrac{a_i-a_j}{p}\rceil\times p+\lfloor \dfrac{a_i-a_j-1}{p}\rfloor\times d$$

看似不太好做，但是有一个很好的性质，就是 $\lceil \dfrac{x+y}{p}\rceil$ 和 $\lceil \dfrac{x}{p}\rceil+\lceil \dfrac{y}{p}\rceil$ 只差 $O(1)$。

所以我们可以假装就是 $\lceil \dfrac{x}{p}\rceil+\lceil \dfrac{y}{p}\rceil$,然后通过对 $a_i\mod p$ 的分讨把 $O(1)$ 给补回来，那么只需要一个线段树即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010,M=1e12;
int a[N],val[N],f[N];
struct node{
	int l,r,s;
}tr[N<<5];
int rt;
int b,p,d,n,tot;
void update(int l,int r,int &p,int x,int v){
	if(!p){tr[p=++tot]={0,0,M};}
	tr[p].s=min(tr[p].s,v);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)update(l,mid,tr[p].l,x,v);
	else update(mid+1,r,tr[p].r,x,v);
}
int query(int l,int r,int p,int a,int b){
	if(!p)return M;
	if(l>b||r<a)return M;
	if(a<=l&&r<=b)return tr[p].s;
	int mid=(l+r)>>1;
	return min(query(l,mid,tr[p].l,a,b),query(mid+1,r,tr[p].r,a,b));
}
int get(int x){
	return f[x]-val[x]-(a[x]+1)/p*d;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>b>>p>>d>>n;
	for(int i=1;i<=n;i++)cin>>a[i],val[i]=a[i]-a[i]%p;
	f[0]=0;update(0,M,rt,0,get(0));
	for(int i=1;i<=n;i++){
		f[i]=1e19;
		f[i]=min(f[i],val[i]+a[i]/p*d+query(0,M,rt,p-1,p-1));
		f[i]=min(f[i],val[i]+a[i]/p*d+query(0,M,rt,0,a[i]%p-1)+p);
		f[i]=min(f[i],val[i]+a[i]/p*d+query(0,M,rt,a[i]%p,a[i]%p));
		f[i]=min(f[i],val[i]+a[i]/p*d+query(0,M,rt,a[i]%p,p-2)-d);
		update(0,M,rt,a[i]%p,get(i));
	}
	int ans=1e19;
	for(int i=0;i<=n;i++)ans=min(ans,f[i]+b-a[i]+(b-a[i]-1)/p*d);
	cout<<ans<<'\n';
	return 0;
}