记录一道简单的省选题

难度：省选/NOI-（个人感觉难度虚高）

题目描述

        传说很久以前，大地上居住着一种神秘的生物：地精。
        地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

Samplle input

4 7

Sample output

3

说明

【样例说明】
共有十种可能的情况，分别为：
        1324        1423        2143        2314        2413
        3142        3241        3412        4132        4231
        加下划线的数位表示可以设立瞭望台的山峰，其它表示可以设立酒馆的山谷。
【数据规模和约定】
        对于20%的数据，满足N≤10；
        对于40%的数据，满足N≤18；
        对于70%的数据，满足N≤550；
        对于100%的数据，满足3≤N≤4200，P≤1e9。

题解

        可以说是一道很水的省选题了。考察动态规划，题目本质上是对于一个数N，求1~N能够组成的大小相间的排列方案数。
        令dp(x，p，y)表示长度为x，末尾数字作p(0为山谷、1为山峰)，末尾数不超过y时的方案数，则有状态转移方程：

        对状态转移方程的理解是本题唯一难点。之后将数组第一维滚动掉，最终空间复杂度O(N)，时间复杂度O(N2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>

#define N 4200+1
using namespace std;
int n, mod, dp[2][2][N] = {0};
bool k = false;

//0山谷，1山峰
int main() {
    cin >> n >> mod;
    dp[0][0][2] = dp[0][0][1] = dp[0][1][2] = 1;
    for (int i = 3; i <= n; i++) {
        k = !k;
        for (int j = 1; j <= i; j++) {
            dp[k][0][j] = (dp[k][0][j - 1] + (dp[!k][1][i - 1] - dp[!k][1][j - 1] + mod) % mod) % mod;
            dp[k][1][j] = (dp[k][1][j - 1] + dp[!k][0][j - 1]) % mod;
        }
    }
    cout << (dp[k][0][n] + dp[k][1][n]) % mod;
    return 0;
}