@[Mikaela](/user/242718) 从高到低排序，DP就好了
by Oops！ @ 2020-01-23 12:20:39
@[Oops！](/user/238918) 可是我超时了(这不是O(N^2)吗)
by Mikaela @ 2020-01-23 12:25:47
这个做法行不行:
```
#include<iostream>
#include<algorithm>
#define N 100010
using namespace std;
const int mod=99824353;
int n,k,f[N],l=1,r=1,q[N]={1},a[N],sum=1;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(a[i]>k) break;
if(a[i]<=k) f[i]=1;
}
for(int i=2;i<=n;i++)
{
while(l<=r&&(a[i]-a[q[l]])>k) sum-=f[q[l]],l++;
q[++r]=i;f[i]=(f[i]+sum)%mod;
sum=(sum+f[i])%mod;
}
cout<<f[n]<<endl;
return 0;
}
```
by Mikaela @ 2020-01-23 12:26:11
维护前缀和？
by zhy137036 @ 2020-01-23 12:34:24
@[zhy123456](/user/178294) 我是这么想的,用队列维护,您能不能看一下对不对呢
by Mikaela @ 2020-01-23 12:36:01
@[zhy123456](/user/178294) 谢谢dalao
by Mikaela @ 2020-01-23 12:36:23
树按高度$h_i$从小到大排序，设$f_i$表示从第$i$棵树开始跳能跳到地面的路径数量，记录一个前缀和$s_i=\sum\limits_{j=1}^if_j$，那么转移是
$f_i=\sum\limits_{j=k}^{i-1}f_j=s_{i-1}-s_k$，其中$k$是满足$h_i-h_k\leqslant K$的最大的$k$。
这个$k$值可以二分找到，总复杂度$O(n\log n)$
另外还可以线段树优化建图+DAG求最长路，也是$O(n\log n)$（逃
by GKxx @ 2020-01-23 12:51:01
哦 可以用队列维护，就不用二分查找了，可以去掉一个$\log$，但排序成了复杂度的瓶颈，如果输入按照从小到大给出的话就可以$O(n)$
by GKxx @ 2020-01-23 12:52:58
@[GKxx](/user/72071) 好的谢谢dalao,我的就是这样
by Mikaela @ 2020-01-23 12:54:59
@[GKxx](/user/72071) 线段树优化建图+DAG求最长路 ,dalao这个能说一下具体做法吗
by Mikaela @ 2020-01-23 13:03:17