题解：P10761 [BalticOI 2024] Trains
xiaoliebao1115
·
·
题解
大佬写的题解都太抽象了，这一篇题解献给每一个蒟蒻们。
朴素动态规划
从左到右进行动态规划即可，就是 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 的铁路线继续往下一个站点开。
$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
```cpp
#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$ 或者是超出范围的时候要特判一下，记得赋初值。