題目描述

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

題目思路

dp。

定義 $d{p}_{i,j}$ 為前 $i$ 個數的排列中恰好有 $j$ 個小于號的排列總數。

考慮將數字 $i$ 插入到前 $i?1$ 個數的排列中不同的位置：

• 如果插入到最前面，會增加一個大于號。
• 如果插入到最后面，會增加一個小于號。
• 如果插入到已有的小于號中間，原來的小于號會被破壞，變成一個大于號和一個小于號，所以會增加一個大于號和一個小于號，即小于號數目不變。
• 如果插入到已有的大于號中間，原來的大于號會被破壞，變成一個小于號和一個大于號，即增加一個小于號。

綜上，得出狀態轉移方程
$$d{p}_{i,j}=d{p}_{i?1,j}\times (j+1)+d{p}_{i?1,j?1}\times (i?j)$$

處理一下邊界條件：因為只有一個數字時沒有符號，所以 $d{p}_{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;
} 

---

創作不易，白嫖不好，各位的支持和認可，就是我創作的最大動力，如果喜歡我的文章，給個關注吧！

冰焰狼 | 文

如果本篇博客有任何錯誤，請批評指教，不勝感激 ！