有N个高矮不同的人，求高矮高矮高矮高矮......或者矮高矮高矮高......的排列方法一共有多少种。
假设第N个插入到队伍中的人比前N-1个人都要高，假设他插入的位置为 j ,那么j-1要比j-2矮，j+1要比j+2矮
即 j-2 j-1 j j+1 j+2 是高矮高矮高
所以先选前j-1个人，排列组合C(n-1,j-1)。
dp[i][0]表示插入位置之前的人的排列种数
dp[i][1]表示插入位置之后的人的排列种数
sum[i]为i个人排列满足要求的排列种数
dp[i][0]=dp[i][1]=sum[i]/2对于第n个人放到位置j ,有C(n-1,j-1)*dp[j-1][0]*dp[n-j][1]种情况。
#include<bits/stdc++.h> using namespace std; #define ll long long ll dp[50][50]; ll sum[50]; ll jiecheng(ll a) { ll ans=1; while(a!=0) { ans*=a; a--; } return ans; } ll cal(ll a,ll b) { return jiecheng(a)/jiecheng(a-b)/jiecheng(b); } int main() { memset(dp,sizeof(dp),0); memset(sum,sizeof(sum),0); dp[0][0]=dp[0][1]=1; dp[1][0]=dp[1][1]=1; sum[1]=1; for(int i=2;i<21;i++) { sum[i]=0; for(int j=1;j<=i;j++) { sum[i]+=(dp[j-1][0]*dp[i-j][1]*cal(i-1,j-1)); } dp[i][0]=dp[i][1]=sum[i]/2; } int n, a,b; cin>>n; while(n--) { scanf("%d%d",&a,&b); cout<<a<<" "<<sum[b]<<endl; } return 0; }