题意: 将题意转化为有n个w,和n个h,现在要将他们组成一个2 * n 的字符串,问有多少种组成方式,要求是对于任意一个位置i,0~~i位置中,w的个数不小于h的个数。
表示不知道卡特兰数,也不知道这只是个递推式..............
用常规dp写法,dp[i][j]表示,前i个字符组成的串中,有j个w的总数,如果第i个字符用的是w 则dp[i][j] += dp[i-1][j-1] ; 如果第i个字符用的是h, 则dp[i][j] += dp[i-1][j];
两种情况都有限制条件:第一种必须满足,i - j <= j - 1 第二种必须满足 i - j <= j
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; __int64 dp[66][33]; int n; void solve() { memset(dp,0,sizeof(dp)); dp[1][1] = 1; for(int i=2; i<=2*n; i++) { int span = min(i,n); for(int j=1; j<=span; j++) { if(j <= i) { if(i - j + 1 <= j) dp[i][j] += dp[i-1][j-1]; if(i - j <= j) dp[i][j] += dp[i-1][j]; } } } printf("%I64d\n",dp[2*n][n]); } int main() { while(scanf("%d",&n) && n) { solve(); } return 0; }