题意：给定n个个数1~n。要求他们排成一列满足“波浪型”。第一个大于第二个，第二大于第三个，（或者第一个小于第二个，第二个小于第三个。。）也就是相对的高矮高矮。。。或矮高矮高。。依此类推。求排列总方案数
思路：考虑第I个数，加入已经排好I-1个数的序列中，要怎样放第I个数才能使新的序列合法呢？I是大于前I-1所有的数，放到任意位置都是“高”。所以I插入的这个位置前面的一个数必须相对它前面的数是“矮”，I后面一个数相对它后面的一个数是“矮”。
假设选定的这个位置是j（i的前面有j个人），
用dp[j][0]代表矮开头的且j个数组成的种类数
用dp[j][1]代表矮结尾的且j个数组成的种类数
dp[j][0]和d[I][0]是相等的，因为对称
如果我们知道在j个人的时候有多少是以矮结尾的，有多少是以矮开头的，在从I-1个人中选j个人去组合，就能算出第I个数放到j这个位置种类数。由1，2的状态，递推后面的状态
#include<cstdio> #include<cstring> #define ll long long using namespace std; ll dp[21][2];//0 代表矮开头的 1 代表矮结束的 ll sum[21]; ll C(int n,int m) { ll A=1,B=1; for(int i=n;i>=n-m+1;i--) A*=i; for(int j=2;j<=m;j++) B*=j; return A/B; } int main() { int T; dp[1][0]=dp[1][1]=1; dp[2][0]=dp[2][1]=1; sum[1]=1;sum[2]=2; for(int i=3;i<=20;i++) { sum[i]=dp[i-1][1]+dp[i-1][0];//i-1个数全部放前面 和 全部放后面 for(int j=1;j<i-1;j++) sum[i]+=dp[j][1]*dp[i-1-j][0]*C(i-1,j); dp[i][0]=dp[i][1]=sum[i]/2; } scanf("%d",&T); while(T--) { int a,b; scanf("%d%d",&a,&b); printf("%d %lld\n",a,sum[b]); } }