[原创]51nod 1296 有限制的排列 【动态规划】

Tabris

CSDN动态规划51nod

发布于：2017年6月14日

次浏览

[原创]51nod 1296 有限制的排列 【动态规划】

2017-06-14 16:21:10 Tabris_ 阅读数：349

博客爬取于 2020-06-14 22:39:59
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73246276

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1296
———————————————————————————————————————————
1296 有限制的排列
题目来源： HackerRank
基准时间限制：1 秒 空间限制：131072 KB 分值： 80 难度：5 级算法题 收藏 关注
计算整数集合{1,2,3,4, .... N }满足下列条件的的排列个数：

在位置 a1, a2, ..., aK 小于其邻居（编号从 0 开始）。
在位置 b1, b2, ..., bL 大于其邻居。

输出符合条件的排列数量 Mod 1000000007 的结果。例如：N = 4，a = {1}, b = {2}，符合条件的排列为：

2 1 4 3
3 2 4 1
4 2 3 1
3 1 4 2
4 1 3 2
Input
第 1 行：3 个数 N, K, L，分别表示数组的长度，限制 a 的长度，限制 b 的长度(1 <= N <= 5000, 1 <= K, L <= N)。
第 2 - K + 1 行：每行一个数，对应限制 a 的位置(1 <= ai <= N - 2)
第 K + 2 - K + L + 1 行：每行一个数，对应限制 b 的位置(1 <= bi <= N - 2)
Output
输出符合条件的排列数量 Mod 1000000007 的结果。
Input 示例
4 1 1
1
2
Output 示例
5
———————————————————————————————————————————

解题思路：

首先要知道的是排列的生成，,
对于一个长度为 x 的排列，在 x+1 的位置插入一个元素 a，那么就是将原排列中所有大于等于 a 的数加 1，

对于本题来说，看到 N 的范围就知道是个 O(n^2)的 dp，但是 dp 废，，，

首先对每个位置标上状态，state[i]代表第 i 个位置和前一个位置的大小关系，

还是设 dp[i][j]为第 i 个位置放 j 的情况数，

那么根据状态的不同转移，

对于求和的过程用一个前缀和优化一下复杂度就能降一维，然后就会发现，转移所需要的信息就是前缀和的信息，所以 dp 数组也只需要一维就好了，

附本题代码
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int N,K,L;
int state[5555];
int sum[5555];
int dp[5555];

int main(){
    scanf("%d%d%d", &N, &K, &L);

    int a;
    for (int i=0;i<K;i++){
        scanf("%d",&a);
        state[++a]=1;
        state[a+1]=2;
    }
    for (int i=0;i<L;i++){
        scanf("%d",&a);
        state[++a]=2;
        state[a+1]=1;
    }

    sum[0]=0;
    dp[1]=sum[1]=1;

    for(int i=2;i<=N;i++){
        for(int j=1;j<=i;j++){
            if(state[i]==0) dp[j]=sum[i-1];
            if(state[i]==1) dp[j]=((sum[i-1]-sum[j-1])%MOD+MOD)%MOD;
            if(state[i]==2) dp[j]=sum[j-1];
        }
        for(int j=1;j<=N;j++) sum[j]=(sum[j-1]+dp[j])%MOD;
    }
    printf("%d\n",sum[N]);

    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN