DP搬运工2
题目描述
给你 (n,K),求有多少个 (1) 到 (n) 的排列,恰好有 (K) 个数 (i(1<i<n)) 满足 (a_{i-1},a_{i+1}) 都小于 (a_i) 。
输入格式
一行两个整数 (n,K)。
输出格式
一行一个整数 (ans) 表示答案 (mod 998244353) 。
样例
样例输入1
4 1
样例输出1
16
样例输入2
10 3
样例输出2
1841152
数据范围与提示
对于 (25\%) 的测试点,(1leqslant n,K leqslant 10) ;
对于 (50\%) 的测试点,(1leqslant n,K leqslant 100) ;
对于 (100\%) 的测试点,(1leqslant n,K leqslant 2000) ;
保证数据有梯度
分析
同样的预设型 (dp) ,但是要简单一些。我们这次只需要考虑有几个符合条件即可。所以我们定义 (f[i][j]) 为插入 (i) 的时候,有 (j) 个满足要求的数。我们仍然按照插入位置分情况。
转移肯定是从 (f[i-1][j]) 转移来,那么我们考虑一下,什么情况下加一个数但是符合要求的数量不变:
- 1、放到之前符合要求的某一组里,多了一组少了一组,相当于没变化。
- 2、放到两个端点的时候不变。
其他情况都是不加的。然后愉快的转移
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 2e3+10;
const int mod = 998244353;
int n,k;
int f[maxn][maxn];
int main(){
scanf("%d%d",&n,&k);
//初始化
f[1][0] = 1;
f[2][0] = 2;
for(int i=3;i<=n;++i){
int jl = min(k,i>>1);//最多有i除以2的满足的情况。
for(int j=0;j<=jl;++j){//枚举所有的位置
if(f[i-1][j] == 0)continue;
f[i][j] = (f[i][j] + f[i-1][j] * 1LL * ((j+1) << 1))%mod;//放到之前的某个里或者边界,此时满足条件的不加
f[i][j+1] = (f[i][j+1] + f[i-1][j] * 1LL * (i-((j+1) << 1)))%mod;//放到其他地方,满足条件的加一
}
}
printf("%d
",f[n][k]);
return 0;
}