The King’s Ups and Downs HDU-4489(dp+好題を繰り返す)

トランスファゲート
題意:nを1つ与えて、それから1-nを使って波形データを構築して、何組構築できますか?
问题解:まず小さい时から大きい时まで割り込むことを考えて、最后のこの最大の数を挿入する时、どのように挿入して入ることができますか?この数の前が高低で、後が低高の形式でない限り、dp[i][0]で波形に合致し、最後が高低の形式を表し、dp[i][1]で波形に合致する冒頭が低高の形式であることを表し、その後、i-1人の中からj人を選んでこのdp[j][0]になるようにし、選法は全部でc[i-1][j]種あり、この組合せ数は配列繰返しの形式で出すことができる.転送ゲートを参考にして、あとで繰返し方程式を書くことができますが、このときの総案数はans=dp[j][0]*dp[i-j-1]*c[i-1][j]、(0<=j<=i-1)の後にdp[i][0]とdp[i][1]を考えなければなりません.このansを平分するかどうか、答えははい、iが偶数の时、最后の2つは高低と头の2つが低高正好平分の総方案数で、iが奇数の时、最后の2つは高低と头の2つが低高でちょうど平分の総方案数で、最后に出力する时1特判下でいいです.
コードを添付:

#include

using namespace std;

typedef long long ll;

const int maxn=20+5;

ll dp[maxn][2],c[maxn][maxn];

void getc()
{
    for(int i=0;i