[sdoi 2010][bzoj 1925]地精部落（dp）

题干：

地精喜欢住在连绵不绝的山脉中。一座长度为N的山脉 H可分 为从左到右的N段，每段有一个独一无二的高度 Hi，其中Hi是1到N之间的正整数。 如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边 缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。酒馆可以设立在山谷之中。地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台,地精们希望这N段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。 现在你希望知道，长度为N 的可能有地精居住的山脉有多少种。两座山脉A 和B不同当且仅当存在一个i，使得 Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

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

题解:

首先，我们的目标序列一定是山峰与山谷交替出现的，也就是说，当x位置是山峰，我们就要从剩下的且比x处山峰高度小的数中挑一个，放到x+1位置上，反之要挑大的数。

根据题干中的“连绵不绝的山脉”，我们可以知道1～n中的所有数在n个山峰中都出现且仅出现一次。。。（一本正经地说这么显然的东西。。。）既然是“连绵不绝”，我们手模几个小样例就可以发现

0%输出样例

40%状压
　　先看一下数据范围，发现40%的点其实是可以作为状压dp来写，但dp表示什么呢？一般来说，状压dp[i][j]表示枚举到第i位时状态为j时的方案数（本题所求的是方案数）。而到本题适用吗？想一下：枚举到第i位时我安置的房子状态为j。。。好像是可以，但状态怎么表示？010101或101010？不可取。反正本蒟蒻作者没有想到，咕咕咕。。。（40%的算法都想不到。。。）其实状态

70%  O(n³)

　　550³勉强能承受。我们记录状态为dp[i][j][0/1],i表示剩下i个数，j表示有j-1个数小于刚刚选择的数，当下标为0时，表示山谷，当下标为1时，表示山峰（其实正反都可以）。根据我们所定义的转移方程，dp[i][j][0]可以影响dp[i-1][j~i][1]，dp[i][j][1]可以影响dp[i-1][1~j-1][0]。那么我们就可以初始化dp[n][0][0]= 未完。。。。。。

100% O(n²)

https://www.cnblogs.com/ac-evil/p/10338316.html

https://www.cnblogs.com/Yu-shi/p/11116895.html

https://www.cnblogs.com/cj-chd/p/9967904.html

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #define $ 4444
 4 using namespace std;
 5 int m,n,mod,dp[2][$],ans;
 6 signed main(){
 7     scanf("%d%d",&n,&mod);
 8     if(n==1){    printf("%d\n",1%mod); return 0;    }
 9     dp[0][1]=1;
10     for(register int i=2,now=1,las=0;i<=n;++i,las=now,now^=1){
11         for(register int j=1;j<=i;++j)
12             dp[now][j]=(dp[now][j-1]+dp[las][i-j+1])%mod;
13     }
14     for(register int i=1;i<=n;++i) ans=(ans+dp[(n-1)%2][i])%mod;
15     printf("%d\n",(ans<<1)%mod);
16 }

code

[sdoi 2010][bzoj 1925]地精部落（dp）

原文：https://www.cnblogs.com/OI-zzyy/p/11131686.html