2022杭电多校9 Matryoshka Doll

input:

2
4 3 2
1 2 3 4
4 2 1
1 1 2 2
output:

2
4 3 2
1 2 3 4
4 2 1
1 1 2 2

题目大意：有𝑛个套娃，大小为𝑎1 ≤ 𝑎2 ≤ ... ≤ 𝑎𝑛，现在要将这些套娃分成𝑘组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求≥ 𝑟，求方案数。

解题思路：DP。

状态表示：dp[i][j]表示前i个套娃按要求分成j组的方案数。

状态转移：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*(j-temp)，意思是当前第i个套娃可以单独作为一组，也可以和之前的套娃共同作为一组，temp表示对于1<=z

上代码：

#include 
#include 
#include 
#include 
using namespace std;
const int N=5010;
const int mod=998244353;
long long n,k,r,a[N];
long long dp[N][N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%lld %lld %lld",&n,&k,&r);
		for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
		memset(dp,0,sizeof dp);
		dp[0][0]=1;
		int p=0;
		for(int i=1;i<=n;i++)
		{
			while(p+11]+r
			p++;
			long long temp=i-p-1;
			for(int j=temp;j<=k;j++)
			dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*(j-temp)%mod)%mod;
		}
		printf("%lld\n",dp[n][k]); 
	}
	return 0;
}