「SDOI2010」地精部落 - DP

我们称一个排列是合法的,当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。

求长度为 的合法排列数量。

链接

BZOJ 1925

题解

题目相当于要求 ~ 的合法排列数。

表示 ~ 的排列,第一个数为 ),且第二个数比第一个数小的方案数。

考虑第二个数,当第二个数小于 时,其方案数为第一个数为 时的方案数,即 。 当第二个数等于 时,从第二个数开始,是一个 ~ 的排列,这个排列的第二个数比第一个数。如果将每个数 变成 ,那么就变成原有的第二个数比第一个数小的情况了。即

所以转移方程为

答案为 ,因为要考虑第二个数大于第一个数的方案数所以乘

代码

不使用滚动数组,内存 30M+ 是可以过的。

#include <cstdio>

const int MAXN = 4200;

int n, p;
int _f[MAXN * (MAXN + 1) / 2];
int *f[MAXN + 1];

inline void init() {
    int *curr = _f;
    for (int i = 0; i < n; i++) {
        f[i] = curr;
        curr += i + 1;
    }
    // printf("%ld %d\n", curr - _f, n * (n + 1) / 2);
}

int main() {
    scanf("%d %d", &n, &p);
    init();

    f[1][1] = 1;
    for (int i = 2; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            f[i][j] = (f[i][j - 1] + f[i - 1][i - j]) % p;
            // printf("f[%d][%d] = %d\n", i, j, f[i][j]);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + f[n - 1][i]) % p;

    printf("%d\n", ans * 2 % p);

    return 0;
}

使用滚动数组之后,时间也快不少。

#include <cstdio>

const int MAXN = 4200;

int n, p;

int main() {
    scanf("%d %d", &n, &p);

    static int f[2][MAXN];
    f[1 % 2][1] = 1;
    for (int i = 2; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            f[i % 2][j] = (f[i % 2][j - 1] + f[(i - 1) % 2][i - j]) % p;
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + f[(n - 1) % 2][i]) % p;

    printf("%d\n", ans * 2 % p);

    return 0;
}