ACM模版

描述

题解

个人感觉，这个应该算是数位 dp。

先通过处理输入数据获取一个 state[]，表示每相邻两项之间的大小关系，state[i] = 0，表示无特别关系，state[i] = 1 表示第 i 项小于第 i - 1 项，state[i] = 2 表示第 i 项大于第 i - 1 项。

接着搞一个 dp[i][j] 表示由前 i 个数组成的序列且第 i 位为 j 的合法情况数。在规划的过程中，针对不同的 state[i]，对应不同的状态转移（具体转移方程看代码吧），这里涉及到一个最后一位数 j 插入序列的思维，可以看做把前边的每一种排列中大于等于 j 的数 ++，也就可以达到空出 j 这个数将其插入的效果。

在这里引入一个 sum[j]，表示为前一轮状态下，最后一位小于等于 j 的情况的和。也就是说，当规划到第 i 位时，sum[j] 表示前 i - 1 位数组成的序列的合法情况的 dp[i - 1][j] 的前缀和。这是为了降低复杂度，将三层循环降低为两层，复杂度从 O(n^3) 降低为 O(n^2)。

最后还使用了一个数据结构的优化——滚动数组，降低了内存的消耗，直接将二维数组降低为一维，原本打算将第一维减小到2，构建一个经典的滚动数组，可是后来发现由于状态转移方程比较特殊，根本没有直接用到过前一轮的状态，而是完完全全依赖于 sum[j]，所以直接搞成一个一维的 dp[j] 即可了。

就这样子，没毛病了。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 5e3 + 10;
const int MOD = 1e9 + 7;

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

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];
            }
            else if (state[i] == 1)
            {
                dp[j] = ((sum[i - 1] - sum[j - 1]) % MOD + MOD) % MOD;
            }
            else
            {
                dp[j] = sum[j - 1];
            }
        }
        for (int j = 1; j <= i; j++)
        {
            sum[j] = (sum[j - 1] + dp[j]) % MOD;
        }
    }

    printf("%d\n", sum[N]);

    return 0;
}