题目描述

https://onlinejudge.org/external/14/p1485.pdf

题目思路

dp。

定义 $dp_{i,j}$ 为前 $i$ 个数的排列中恰好有 $j$ 个小于号的排列总数。

考虑将数字 $i$ 插入到前 $i - 1$ 个数的排列中不同的位置：

如果插入到最前面，会增加一个大于号。
如果插入到最后面，会增加一个小于号。
如果插入到已有的小于号中间，原来的小于号会被破坏，变成一个大于号和一个小于号，所以会增加一个大于号和一个小于号，即小于号数目不变。
如果插入到已有的大于号中间，原来的大于号会被破坏，变成一个小于号和一个大于号，即增加一个小于号。

综上，得出状态转移方程
$dpi,j=dpi−1,j×(j+1)+dpi−1,j−1×(i−j)dp_{i,j} = dp_{i-1,j} \times (j + 1) + dp_{i-1,j-1} \times (i - j)$

处理一下边界条件：因为只有一个数字时没有符号，所以 $dp_{1,0} = 1$ 。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll n,k,dp[1010][1010];
int main(){dp[1][0] = 1;for(int i = 2;i <= 1000;i++){for(int j = 0;j < 1000;j++){dp[i][j] = (dp[i - 1][j] * (j + 1) + dp[i - 1][j - 1] * (i - j)) % mod;}}while(cin >> n >> k) cout << dp[n][k] << endl;return 0;
}