动态规划-基础|uva 1485 - Permutation Counting(递推) UVA|训练指南-第二章|GRADE:D

题目链接：uva 1485 - Permutation Counting
题目大意：给定n和k，要求求一个由1~n组成的序列，要求满足ai>i的i刚好有k个的序列种数。
解题思路：dp[j][i]表示长度为i，j个位置满足的情况。

dp[j+1][i]+=dp[j][i]?(j+1);
1, (3), (4), 2: 括号位置代表ai>i,既满足位置,此时i = 4， j = 2.

-> 1, (3), (4), 2, 5 1 种，在最后追加
-> 1, (5), (4), 2, 5
1，(3), (5), 2, 4 j 种，与满足的位置交换，因为新追加的数肯定为当前最大的数，所以满足条件的个数不变

dp[j+1][i+1]+=dp[j][i]?(i?j);
【动态规划-基础|uva 1485 - Permutation Counting(递推)】 -> (5), (3), (4), 2, 1
-> 1, (3), (4), (5), 2 i-j 种，与不满足的位置交换。

#include #include #include using namespace std; typedef long long ll; const int maxn = 1000; const ll MOD = 1e9+7; int N, K; ll dp[maxn+5][maxn+5]; void init () { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i <= maxn; i++) { for (int j = 0; j <= i; j++) { dp[j][i+1] = (dp[j][i+1] + (j + 1) * dp[j][i]) % MOD; dp[j+1][i+1] = (dp[j+1][i+1] + (i - j) * dp[j][i]) % MOD; } } }int main () { init(); while (scanf("%d%d", &N, &K) == 2) { printf("%lld\n", dp[K][N]); } return 0; }