[Sdoi2010]地精部落

题面：

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

仅含一行，两个正整数 N, P。

仅含一行，一个非负整数，表示你所求的答案对P取余之后的结果。

样例输入

4 7

样例输出

对于 20%的数据，满足 N≤10；
对于 40%的数据，满足 N≤18；
对于 70%的数据，满足 N≤550；
对于 100%的数据，满足 3≤N≤4200，P≤ $10910^9109$

分析：

　　首先，强烈谴责将此题放到数学中

　　主流算法貌似是一个什么波动序列（本人不会）

　　拿过题面看到数据范围首先想到状压（20%），后来在whs大神的启发下，发现用状压保存山脉的状态没什么卵用。这里有个比较重要的性质：及维护一个固定长度的山脉，只要保证山峰高度不同，那么方案数是固定的，与山峰具体高度无关（有点像Perm排列计数）。所以只要枚举山脉长度，将新山峰插入转移即可。

　　$dp[k][len][i]$为考虑到的山脉长度为$len$,山脉末尾山峰的相对高度排名为i，是山峰还是谷地的方案数。

　　$dp[k][len][i]=∑dp[k $^$ 1][len-1][s]$

　　如果为山峰，$s$属于$（1，i-1）$，因为在原山脉排名为$s$，在新山脉排名也为s

　　为谷地时，$s$属于$（i，len-1）$，在新山脉中所要的其实是$（i+1，len）$，但除去了$i$，在原山脉实际为$（i，len-1）$

 1 #include<iostream>
 2 #include<cstdio>
 3 #define MAXN 4210
 4 using namespace std;
 5 int N;
 6 int P;
 7 int dp[2][MAXN][MAXN];
 8 int res;
 9 int main(){
10     scanf("%d%d",&N,&P);
11     dp[0][1][1]=dp[1][1][1]=1;
12     for(int len=2;len<=N;++len)
13         for(int i=1;i<=len;++i){
14             for(int s=i;s<len;++s)
15                 dp[0][len][i]=(dp[0][len][i]+dp[1][len-1][s])%P;
16             for(int s=i-1;s>=1;--s)
17                 dp[1][len][i]=(dp[1][len][i]+dp[0][len-1][s])%P;
18         }
19     for(int i=1;i<=N;++i)
20         res=(res+dp[0][N][i]+dp[1][N][i])%P;
21     printf("%d
",res%P);
22 }

70%

　　对，T了，能看到4200×4200，时间长空间大，考虑滚动数组和前缀和即可

最后

#include<iostream>
#include<cstdio>
#define MAXN 4210
using namespace std;
int N;
int P;
int dp[2][2][MAXN];
int res;
int qsum[2][2][MAXN];
int main(){
    scanf("%d%d",&N,&P);
    int now=0,past=1;
    dp[past][0][1]=dp[past][1][1]=1;
    qsum[past][0][1]=qsum[past][1][1]=1;
    for(int len=2;len<=N;++len){
        for(int i=1;i<=len;++i){
            dp[now][0][i]=qsum[past][1][i];
//            printf("%d 0 %d %d
",len,i,dp[now][0][i]);
            qsum[now][0][i]=(qsum[now][0][i-1]+dp[now][0][i])%P;
        }
        for(int i=len;i>=1;--i){
            dp[now][1][i]=qsum[past][0][i-1];
//            printf("%d 1 %d %d
",len,i,dp[now][1][i]);
            qsum[now][1][i]=(qsum[now][1][i+1]+dp[now][1][i])%P;
        }
        now=past;past^=1;
    }
    printf("%d
",(qsum[past][0][N-1]+qsum[past][1][2])%P);
}

100%