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