从前有一个神奇的OJ

上面有一道神奇的线性DP题

题目描述：

有n 个俄罗斯套娃，n 个套娃的大小从小到大分别为 a1,a2,...,an。在俄罗斯套娃中，相邻两个套娃之间的大小差至少为 r。准确地讲，一个套娃 河以被套在另一个套娃j里面，当且仅当它们的大小满足 ai+r<=aj。 你希望把 n 个套娃分成k组，每组的所有套娃都可以按”一个套一个”的形式套成一堆组由编号分别为 c1,C2,...,cm(1 < c < c2 <...< cm n)组成的套娃可以套成一堆，当且仅当所有的 1<i<m, a[i]+r<=a[i+1] 你想知道有多少种方式，将套娃分成k组，每组都能被套成一堆。答案对998244353取模。 Note: {1,2,3,4和3,4,1,2被认为是一种方式。 输入格式 第一行输入三个整数n,k,r(1 <=k<=n<=5000,1<=r<=10^9，分别表示套娃的个数，需要分成的堆数，以及相邻套娃之间需满足的大小差 第二行输入n 个整数 al,a2,...,an (1 < a a2 ...< an < 10，表示n个套娃的大小。 输出格式 一行一个正整数，表示方案数对998244353 取模后的答案

样例1：

4 3 2

1 2 3 4

输出：

3

样例2：

4 2 1

1 1 2 2

输出：

2

然后，我灵感打发 写道：

//code by Hacker Zhu Yifan
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,k,r;
bool now=0,last=1;
vector<int> val,dp[2];
signed main(void){
    cin >> n >> k >> r;
    val.assign(n,0);
    for(int i=0;i<n;i++){
        cin >> val[i];
    }
    dp[now].resize(1,1);
    for(int i=0;i<n;i++){
        now=!now,last=!last;
        dp[now].assign(min(i+1,k)+1,0);
        int cnt=0;
        for(int j=0;j<i;j++){
            cnt+=(val[j]+r>val[i]);
        }
        for(int j=0;j<=min(i+1,k);j++){
            if(j>0) dp[now][j]=(dp[now][j]%mod+dp[last][j-1]%mod)%mod;
            if(j<dp[last].size()) dp[now][j]=(dp[now][j]%mod+(max((int)0,j-cnt)%mod)*(dp[last][j]%mod))%mod;
        }
    }
    cout << dp[now][k] << endl;
    return 0;
}

然后就开门红了