笔试刷题-百度2018-06-21

题目描述：

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

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

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

输入例子1:
5 2

输出例子1:
66

*/

思路如下：

K个小于好把n给数分成了k+1个降序序列
descSeq1 descSeq2 ... descSeq(k+1)
其中descSeq也可能是单独一个数而已也教程降序序列
dp[n][k]表示用前1-n个数全排列, 用k个小于号和n-1-k给大于号分割的合法数目
dp[n][k]可以由两种部分构成 dp[n-1][k] dp[n][k-1]、

dp[n-1][k]要变成dp[n][k]就是在原来的1-n-1的全排列中插入一个n然后使得小于号数目不增加
那么只能放在descSeq1 或 descSeq2...或descSeq(k+1)相应序列的最左边这样才不会增加小于号数目
这样一个原来在dp[n-1][k]中的合法序列插入n后对应了 k+1个新的序列

dp[n][k-1]要变成dp[n][k]就是在1-n-1全排列中插入一个n使得小于号数目增加1
descSeq1 descSeq2...descSeq(k)
可以插入在一个descSeq中见的位置
原来有n-1个数那么n插入的位置有n个位置，但是不能插入在descSeq的最左端的位置这样不增加小于号
那么一共有k个descSeq那么只能插入的位置n-k

n>k
dp[n][k]=(k+1)dp[n-1][k]+(n-k)dp[n-1][k-1]

n>=2
base case:
dp[n][k]=0(n<=k)

dp[n][0]=1

代码如下：

#include<stdio.h>
#include<iostream>

#define MAX_N 1005
#define MAX_K 1005
#define MOD 2017

using namespace std;

int dp[MAX_N][MAX_K];

int main(){
    int N, K;
    scanf("%d%d", &N, &K);
    for(int n=0; n<=N; n++)
        dp[n][0]=1;
    for(int n=2; n<=N; n++){
        for(int k=0; k<n; k++){
            dp[n][k]=((k+1)*dp[n-1][k])%MOD+((n-k)*dp[n-1][k-1])%MOD;
            dp[n][k]%=MOD;
        }
    }
    printf("%d", dp[N][K]);
    return 0;
}