自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 23:00:58，当前版本为作者最后更新于2024-08-11 16:37:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大佬写的题解都太抽象了，这一篇题解献给每一个蒟蒻们。

朴素动态规划

从左到右进行动态规划即可，就是 $dp_i=\sum dp_j$，这里的 $j$ 都有一条从 $j$ 出发的火车路径经停 $i$，特别的 $dp_1=1$。

文中的 $dp_i$ 就表示的是从维尔纽斯开始到 $i$ 结束的方案数总和，这个应该都能理解。最后 $ans=\sum dp_i$。

根号分治

情况 $1$

先令 $b=\sqrt{n}$，很容易发现对于 $d>b$ 的情况来讲最多只有 $b$ 个位置可以从当前位置转移，总复杂度 $O(n\sqrt{n})$。

情况 $2$

考虑 $d\le b$ 的情况，注意到这里的 $d$ 的种类数最多不会超过 $\sqrt{n}$ 个。所以我们开一个数组 $f_{i,j}$ 表示最后经过一个 $d=j$ 的路线到达 $i$ 的总方案数，注意，这个数组只记录 $j\le b$ 的情况。

我们可以得到一些转移方程：$f_{i+j,j}=f_{i+j,j}+f_{i,j}$，这个表示把这条 $d=j$ 的铁路线继续往下一个站点开。

$dp_i=dp_i+f_{i,j}$，这里的 $dp_i$ 已经保存了 $d\le b$ 的所有答案，加上剩余部分即可。

$f_{i+d,d}=f_{i+d,d}+dp_i$，这个表示一条从 $i$ 开始的铁路线，$i+d$ 就是第一个停下来的地方，通过向这个地方转移，可以让 $i+d$ 根据前面的式子向后面停下来的位置转移。

但是考虑到从一个地方开始的火车经停站数量有限，所以有 $f_{i+d\times(x+1),d}=f_{i+d\times(x+1),d}-dp_i$，因为从 $x+1$ 往后就不能再停车了，正确性是显然的，相当于把 $f_{i+d,d}=f_{i+d,d}+dp_i$ 这个式子中增加的 $dp_i$ 给减掉，有点类似于差分的思路。

这边的每次转移都是 $O(1)$，并且 $f_{i,j}$ 大小是 $n\sqrt{n}$ 的，所以整个程序总时间复杂度 $O(n\sqrt{n})$。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nn=1e5+5,B=317,mod=1e9+7;
int n,f[nn][B],dp[nn],ans;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	int b=sqrt(n);
	dp[1]=1;
	for(int i=1;i<=n;i++){
		int d,x;
		cin>>d>>x;
		for(int j=1;j<=b;j++){
			if(i+j<=n) f[i+j][j]=(f[i+j][j]+f[i][j])%mod;
			dp[i]=(dp[i]+f[i][j])%mod;
		}
		ans=(ans+dp[i])%mod;
		if(d==0) continue;
		if(d>b){
			for(int j=i+d,k=1;j<=n&&k<=x;j+=d,k++)
			dp[j]=(dp[i]+dp[j])%mod;
		}
		else{
			if(i+d<=n) f[i+d][d]=(f[i+d][d]+dp[i])%mod;
			if(i+d*(x+1)<=n) f[i+d*(x+1)][d]=(f[i+d*(x+1)][d]-dp[i]+mod)%mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

这里需要注意的是在 $d=0$ 或者是超出范围的时候要特判一下，记得赋初值。