LuoguP2467「SDOI2010」题解

发表于 更新于

求解摆动数列的动态规划

题目描述

传说很久以前，大地上居住着一种神秘的生物：地精。

地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。

如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。

类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。

地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。

地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。

地精们希望这N段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。

现在你希望知道，长度为N的可能有地精居住的山脉有多少种。两座山脉A和B不同当且仅当存在一个i，使得Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

Inputs and Outputs examples

Inputs’ e.g. #1

1
4 7

Outputs’ e.g. #1

1
3

说明

【数据规模和约定】

对于20%的数据，满足N≤10；

对于40%的数据，满足N≤18；

对于70%的数据，满足N≤550；

对于100%的数据，满足3≤N≤4200，P≤1e9。

分析

首先认真读过题的选手一定知道题意的目的是波动数列.

我们首先要明白波动数列的性质:

在一个波动序列中,若$i$和$i+1$不相邻,那么将他们交换可以得到一个新的波动数列

我们设$dp_{i,j}$表示我们选用$1-n$这$n$个数,且第一个数为$j$的方案数.

那么显然答案就是$\sum_{i=1}^n dp_{n,i}$.

首先我们考虑$j$和$j-1$不相邻时的方案数,根据上面那条性质,我们可以推出在这种情况下,$j$作为序列头所有的方案数与$j-1$作为头的方案数相同.

然后如果$j$和$j-1$相邻呢?

我们假设$j$为凸出部分,那么显然与他相邻的$j-1$一定为凹进部分,后面的数一定在$[1,j-1) \bigcup (j,n]$上取值.

那么我们考虑求$i-1$个数，$j-1$为头，且$j-1$为山谷的方案数.

首先我们发现这$i-1$个数的取值不一定是$[1,i-1]$, 没关系,我们把他全$-1$就可以保证相对大小不变了.

那么我们可以列出dp的转移方程式

$$dp_{i,j} = dp_{i,j-1} + dp_{i-1,i-j+1}$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e3 + 10;
int dp[2][MAXN],n,mod;
int ans;
/* functions */
int main(int argc,char *argv[]){
    scanf("%d%d",&n,&mod);
    dp[0][2] = 1;
    FOR(i,3,n,1){
        FOR(j,2,i,1){
            dp[i & 1][j] = (dp[i & 1][j-1] + dp[(i - 1) & 1][i - j + 1]) % mod;
        }
    }
    FOR(i,2,n,1) ans = (ans + dp[n & 1][i]) % mod;
    printf("%d",(ans<<1)%mod);
    return 0;
}

THE END