Luogu 2467[SDOI2010]地精部落 - DP

Solution

这题真秒啊，我眼瞎没有看到这是个排列

很显然， 有一条性质：

　　第一个是山峰 和 第一个是山谷的情况是一一对应的， 只需要把每个数 $x$  变成 $n-x+1$

然后窝萌定义数组 $f[ i ][ j ]$ 表示有 $i$ 座山， 且第一座山是山谷(即开头上升) 且 高度 $<= j$ 时的方案数。

然后考虑如何转移。

1： 当第一位 $!=j$ 时， 即第一位 $ <= j - 1$， 则可从$f[ i ][j-1]$转移得到

2： 当第一位 $=j$ 时， 窝萌假装第一位不存在， 然后把后面序列 $> j$的数都 -1，

　就得到了一个有$i - 1$座山， 第一座山是山峰且高度 $>=j$ (本来是 $>j$，因为 $-1$, 所以 $>=j$ ) 的方案

　然后引用性质，就是第一座山为山谷 且 高度 $<=(i - 1) -j+1$ 的方案， 即 $f[i -1][i - j]$

 

所以最后的转移方程为： $f[i][j] = f[i][j-1] + f[i-1][i-j]$

 

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
using namespace std;

const int N = 4500;

int n, mod;
int f[2][N], op;

int main()
{
    scanf("%d%d", &n, &mod);
    f[1][1] = 1;
    rep(i, 2, n) rep(j, 1, i)
        f[i % 2][j] = (f[i % 2][j - 1] + f[(i - 1) % 2][i - j]) % mod;
    f[n % 2][n] = f[n % 2][n] * 2 % mod;
    printf("%d\n", (f[n % 2][n] % mod + mod) % mod);
}