不等式数列

链接：https://www.nowcoder.com/questionTerminal/621e433919214a9ba46087dd50f09879
来源：牛客网

度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入描述:

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

输出描述:

输出满足条件的排列数,答案对2017取模。

示例1

输入

5 2

输出

66

刚上手这道题目时，直接想到用全排列再check数组，代码如下：

#include <bits/stdc++.h>
using namespace std;

int check(int a[], int n, int k) {
    int l = n - k - 1;
    for (int i = 0; i < n - 1; ++i) {
        if (a[i] < a[i + 1]) 
            k--;
    }
    for (int i = n - 1; i >= 1; --i) {
        if (a[i] < a[i - 1])
            l--;
    }
    return k == 0 && l == 0;
}

int main() {
    int n, k, cnt = 0;
    scanf("%d%d", &n, &k);
    int a[1000] = {0};
    for (int i = 1; i <= n; ++i)
        a[i] = i;
    do {
        cnt += check(a, n, k);
    }while(next_permutation(a, a + n));
    cout << cnt % 2017 << endl;
    return 0;
}

对这种思路不做过多评价，肯定会超时！

下午再来看这道题，发现用DP来解会很容易！代码如下：

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int dp[1001][1001] = {0};
    for (int i = 1; i <= n; ++i) {
    	for (int j = 0; j <= (i % 2 == 0 ? i >> 1 - 1 : i >> 1); ++j) {
    		if (j == 0) {
    			dp[i][j] = 1;
    		}
    		else if (j == 1) {
    			dp[i][j] = (dp[i - 1][j] * 2 + i - 1) % 2017;
    		}
    		else {
    			dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) % 2017;
    		}
    		dp[i][i - j - 1] = dp[i][j];
    	}
    }
    printf("%d\n", dp[n][k] % 2017);
    return 0;
}

值得一说的是对dp数组的每一个数据都%2017，否则遇到较大一点的数据直接会溢出！