題目描述

將1到n任意排列，然后在排列的每兩個數(shù)之間根據(jù)他們的大小關(guān)系插入“>”和“<”。問在所有排列中，有多少個排列恰好有k個“<”。答案對2012取模。

輸入輸出格式

輸入格式：

?

第一行2個整數(shù)n,k。

?

輸出格式：

?

一個整數(shù)表示答案。

?

輸入輸出樣例

輸入樣例#1：
5 2 輸出樣例#1：
66

說明

對于30%的數(shù)據(jù)：n <= 10

對于100%的數(shù)據(jù)：k < n <= 1000

分析：求方案數(shù)，想不到數(shù)學(xué)方法，用dp來做，看數(shù)據(jù)范圍，應(yīng)該是一個O(nk)的算法，那么設(shè)f[i][j]表示前i個數(shù)中插入了j個'<'號的方案數(shù)，考慮第i個數(shù)的插入，這個數(shù)比前i-1個數(shù)都要大，它插入進(jìn)來后可能會多一個'<'號也可能不會多.如果多了一個'<'號，那么就有i-j個位置可以插入，可以插在隊尾和i-j - 1個大于號的位置，如果沒有多'<'號，那么我們在'<'號的位置插入或者在隊首插入，這樣可以得到式子f[i][j] = f[i-1][j] * (j + 1) + f[i-1][j-1] * (i - j).

#include <cstdio> #include <iostream> #include <cstring> #include <vector> #include <algorithm>using namespace std;const int mod = 2012;int n, k, f[1010][1010];int main() {scanf("%d%d", &n, &k);f[0][0] = 1;for (int i = 1; i <= n; i++){f[i][0] = 1;for (int j = 1; j <= k; j++)f[i][j] = (f[i - 1][j] * (j + 1) + f[i - 1][j - 1] * (i - j)) % mod;}printf("%d\n", f[n][k]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/7535295.html

總結(jié)

以上是生活随笔為你收集整理的noip模拟赛 不等数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。