题目地址：洛谷：【P2467】[SDOI2010]地精部落 – 洛谷、BZOJ：Problem 1925. — [Sdoi2010]地精部落

题目描述

传说很久以前，大地上居住着一种神秘的生物：地精。
地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。
如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。
类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。
地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。
地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。
地精们希望这N段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。
现在你希望知道，长度为N的可能有地精居住的山脉有多少种。两座山脉A和B不同当且仅当存在一个i，使得Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

输入输出格式

输入格式：
输入文件goblin.in仅含一行，两个正整数N, P。

输出格式：
输出文件goblin.out仅含一行，一个非负整数，表示你所求的答案对P取余之后的结果。

输入输出样例

输入样例#1：

4 7

输出样例#1：

3

说明

【数据规模和约定】
对于20%的数据，满足N≤10；
对于40%的数据，满足N≤18；
对于70%的数据，满足N≤550；
对于100%的数据，满足3≤N≤4200，P≤1e9。

题解

40%一看就是个状压，也是我最开始想到的解法。dp[i][j][S]表示选到第i位，最后一位是j，且选数状态为S的方案数，枚举没选的数填上向后+1转移。
N这么小是不是可以暴力打表哇（雾）。
后面这些部分分就需要一些思考了。建议在拿到这道题的时候开始手玩一下这个序列的性质。比如有这么些性质：

1. 如果i和i+1在序列中不相邻，交换它们俩序列仍然是一个波动序列。你可以枚举i和i+1为峰谷的4种情况验证；
2. 把序列中的每个数变为N-这个数+1，序列仍然是波动序列，只是山峰山谷反了一下。

我们需要的是一个方便统计答案的状态，状态中要包含区分不同状态的要素，比如，开头的数字？上面状压的问题在于我不知道下一个要填什么数字，因此我们自然不能让状态受到下一个位置填什么数这个问题的限制。有一种方法是缩小问题的规模，就是先缩小n的范围，解决小问题，然后再向大问题扩展，这样做可行吗？结合上面两个问号之前的猜想，我们可以设计出如下状态：假如我们已经做好了一段序列，而且这段序列用的是[1, i]这些数字，且以j开头，且规定开头是个山峰，设计出的DP状态是dp[i][j]。
现在的问题是如何从小问题向大问题转移，或者说大问题应该如何从小问题中计算答案。我们可以从性质1得知，如果j-1和j不相邻，dp[i][j]中应该包含一个dp[i][j-1]，即交换一次j和j-1形成新的序列。那么另外一部分就是j和j-1相邻，此时j-1是山谷，也就是说，我们只需要求出数字在[1, i]{j}中且j-1为开头的山谷的方案数。这个排除j很烦人，但是如果考虑把这个数列中[j+1, i]的数字全部减1，对于序列的合法性是没有影响的，因此这个等价于数字在[1, i-1]中且j-1为开头的山谷的方案数。我们想到了性质2，如果把序列反一下就好了，因此就变成了(i-1)-(j-1)+1=i-j+1开头的山峰的方案数，这个就是dp[i-1][i-j+1]。结合上面的讨论，方程如下
dp[i][j] = dp[i][j-1] + dp[i-1][i-j+1]
答案就是\sum_{i=2}^N dp[N][i]。复杂度O(n^2)，空间可以滚动数组搞成O(n)的。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 4205;

int n, p;
LL dp[2][MAXN];

int main() {
    n = readint(); p = readint();
    dp[0][2] = 1;
    for(int i = 3; i <= n; i++) {
        for(int j = 2; j <= i; j++) {
            dp[i & 1][j] = (dp[i & 1][j - 1] + dp[i & 1 ^ 1][i - j + 1]) % p;
        }
    }
    LL ans = 0;
    for(int i = 2; i <= n; i++) {
        ans = (ans + dp[n & 1][i]) % p;
    }
    ans = ans * 2 % p;
    printf("%lld", ans);
    return 0;
}