题目大意：
1~n的排列中，要任意一个数要么比它左右的数都大或小，求所有的方案数。
思路：
主要思路：离散。
三个引理：
①在n->n-1的转化过程中，我们删除了一个点后，我们可以将n-1个点视为仍是1~n-1的排列。
②在若排列Pn为一个合法抖动子序列，则交换i∈[1,n)与i+1,必能得到另一个抖动子序列。
③抖动序列的对称性，若存在第一段上升的长度为n的抖动子序列，则以n+1-x代x必能得到一个第一段下降的长度为n的抖动子序列。
fi,j表示有个大小为i的数集{1...i}，然后开头可以是1到j中的任何一个，但是需要是山峰。然后f表示方案数。
然后转移方程fi,j−1部分就是开头为1~j−1先算出来了，方案数加进来。 f{i-1,i-j}则是开头选了j，剩下i−1个数，离散化一下是一个大小为i−1的数集，然后开头必须选1~j−1来保证下降。但是f表示上升，所以取反，然后应该等于fi−1,i−j
另外注意，这题卡内存，64MB，需要滚动数组。
参考：http://blog.csdn.net/ta201314/article/details/41380891
http://blog.csdn.net/vmurder/article/details/44604275
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,i,j,k,mo,dp[2][5000]; 5 6 int main() 7 { 8 scanf("%d%d",&n,&mo); 9 for (dp[1][1]=1,i=2;i<=n;i++) 10 for (j=1;j<=i;j++) 11 dp[k=i&1][j]=(dp[!k][i-j]+dp[k][j-1])%mo; 12 printf("%d\n",(dp[k][n]<<1)%mo); 13 return 0; 14 }转载于:https://www.cnblogs.com/HHshy/p/5775519.html
相关资源：JAVA上百实例源码以及开源项目