AHSOFNU NOIP模拟题-1 T2(DP+乘法原理)

发表于 | 分类于 | | + s

对于$1-n$等类似的排列计数问题，以动态规划和组合数学2种大方向为基本解决方向。
我们从小到大插入数字，因此我们现在插的这个数比现在所有在序列里的数都要大。
这样一来就不需要记录是哪些数字插入了(而只要记录插入到了第几个数字)，同时不需要记录每个数字的具体位置，也不需要记录数字的相对位置，而只需记录相对关系的数目(对本题而言就是有几个“<”)
我们设$dp(i, j)$表示前$i$个数字构成的数列中，恰有$j$个”<”号的方案数(“>”号就有$i-j-1$个)
考虑插入数的位置：
1、插入在两个数关系为”<”之间：
显然这样插入会增加一个“>”，那么有$j+1$个位置可以插，那么有状态转移方程$dp(i, j) += dp(i-1, j) * (j+1)$
2、插入在两个数关系为”>”之间：
显然这样插入会增加一个“<”，那么有$(i-j+1)-1$个位置可以插，那么有状态转移方程$dp(i, j) += dp(i-1, j-1) * (i-j)$
综上所述，$dp(i, j) = dp(i-1, j) * (j+1) + dp(i-1, j-1) * (i-j)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "num"
using namespace std;
const int MAXN = 1000 + 5, MO = 2012;
int n, k, dp[MAXN][MAXN];
void clean() {
}
void solve() {
    clean();
    scanf("%d%d", &n, &k);
    dp[1][0] = 1;
    for (int i=2;i<=n;i++) {
        dp[i][0] = 1;
        for (int j=1;j<n;j++) {
            dp[i][j] = (dp[i][j]%MO + (dp[i-1][j]*(j+1))%MO + (dp[i-1][j-1]*(i-j)%MO))%MO;
        }
    }
    printf("%d\n", dp[n][k]%MO);
}
int main() {
    freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
    solve();
    fclose(stdin), fclose(stdout); 
    return 0;
}

Problem 2 不等数列
【题目描述】
将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。

【输入格式】
第一行2个整数n,k。

【输出格式】
一个整数表示答案。

【样例输入】
5 2
【样例输出】
66
【数据范围】
对于30%的数据：n <= 10
对于100%的数据：k < n <= 1000，

------ 本文结束 ------