JZOJ 5195. 【NOIP2017提高组模拟7.3】A
相当于问将$n$拆分成$k$个正整数之和的拆分数
设$f[n][k]$表示将$n$拆分成$k$个正整数之和的拆分数，那么对于当前的决策，可以将所有数都加$1$，或者新来一个$1$
即$f[n][k] = f[n - 1][k - 1] + f[n - k][k]$
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 5010; 4 int f[N][N], n, k; 5 int main() { 6 scanf("%d%d", &n, &k); 7 f[0][0] = 1; 8 for(int i = 1 ; i <= n ; ++ i) 9 for(int j = 1 ; j <= min(i, k) ; ++ j) 10 f[i][j] = (1ll * f[i - 1][j - 1] + f[i - j][j]) % 998244353; 11 printf("%d\n", f[n][k]); 12 }
转载于:https://www.cnblogs.com/KingSann/articles/9481394.html