hdu4489 The King’s Ups and Downs

Last Edited: Jan 26, 2019 5:13 PM

Tags: acm,dynamic programming

题意

求N个人高矮或矮高依次排列的个数

思路

不妨先排列好i个人显然第i+1个人可以插在中间任何一个位置，若在开头则要求i个人的排列是先上升，若在末尾则要求i个人最后一个人是下降得到的

设DP[i][0] 为开头上升，DP[i][1]为开头下降。显然开头上升和末尾下降是对称的。同理开头下降和末尾上升是对称的。且DP[i][0] 和DP[i][1]应该相等。

所以DP[i+1][0] = DP[j - 1][0] * DP[i - j][1] * C[i-1][j-1]

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define sci(num) scanf("%d",&num)
typedef  long long LL;
const int MAX_N = 25;
LL C[MAX_N][MAX_N],DP[MAX_N][2];
LL sum[MAX_N];
void init() {
   for (int i = 0;i < MAX_N;i++) {
       C[i][0] = C[i][i] = 1;
       for (int j = 1;j < i;j++) {
           C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
       }
   }
   mem(DP,0);
   mem(sum,0);
   DP[0][0] = DP[0][1] = 1;
   DP[1][0] = DP[1][1] = 1;
   sum[0] = 0;
   sum[1] = 1;
   for (int i = 2;i < MAX_N;i++) {
       for (int j = 1;j <= i;j++) {
           sum[i] += DP[j - 1][0] * DP[i - j][1] * C[i -  1][j - 1];
       }
       DP[i][0] = DP[i][1] = sum[i] / 2;
   }
}

int main() {
   init();
   int P;
   sci(P);
   while (P--) {

       int id;
       sci(id); int N;
       sci(N);
       printf("%d %lld\n",id,sum[N]);
   }

   return 0;
}
    ```