The King’s Ups and Downs

题意：给你N个人的身高，他们身高各不相同，问排列是高低高低高低、或低高低高低高的方案数是多少？
图片说明

分析

此问题的阶段性很容易看出来，就是先求出N = 1的排列数，再求出N=2的排列书，然后再求N=3，再求N = i的排列数时，可能要用到N = 1，N = 2,N = 3...N = i-1的排列数。那如何去找前后阶段的关联性，试想一下，假如上一下阶段N = i-1的排列方案已经求了出来，现在要将第i个人插入到此排列中，假如插入到第j个位置，那么需要知道j位置之前j-1个人以高低结尾的方案数，还需要知道j位置之后i-1-j个人以低高开始的方案数，很幸运的是在此阶段之前小于等于i-1的排列数就已经求出来了，他包括高低，低高两种情况排列
所以：
j-1个人以高低结尾的方案数 = j-1排列的方案数/2 (前面阶段已经求出)
i-1-j个人以低高开始的方案数 = i-1-j排列的方案数/2 (前面阶段已经求出)

所以状态表示：
dp[i][0]:表示i个人以高低结尾的方案数
dp[i][1]:表示i个人以低高开始的方案数
sum[i]:i个人的排列数
C[i][j]:从i个人选j个人

状态转移：
sum[i] = C[i-1][j]*dp[j][0]*dp[i-1-j][1]
插入的位置，前面有j个人，i-1是上一阶段的人数

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;

int T,id,N;
ll C[25][25];
ll sum[25];
ll dp[25][2];//dp[i][0]:i个人最后以高低结尾的方案数，dp[i][1]:i个人以低高开始的方案数
void initC(){ //初始化组合数C
    C[1][1] = 1;
    for(int i = 0;i<=20;i++) C[i][0] = 1;
    for(int i = 1;i<=20;i++){
        for(int j = 1;j<=i;j++){
            C[i][j] = C[i-1][j]+C[i-1][j-1];
        }
    }
}
void solve(){
    dp[0][0] = 1,dp[0][1] = 1;dp[1][0] = 1;dp[1][1] = 1;
    sum[1] = 1;
    for(int i = 2;i<=20;i++){
        for(int j = 0;j<=i-1;j++){
            sum[i] += C[i-1][j]*dp[j][0]*dp[i-1-j][1];
        }
        dp[i][0] = dp[i][1] = sum[i]/2; //因为sum[i]包括高低、低高两种情况
    }
}

int main(){
    initC();
    solve();
    cin>>T;
    while(T--){
        scanf("%d%d",&id,&N);
        printf("%d %lld\n",id,sum[N]);
    }
    return 0;
}