The King’s Ups and Downs(HDU 4489,动态规划递推,组合数,国王的游戏)

题意:

给一个数字n,让1到n的所有数都以波浪形排序,即任意两个相邻的数都是一高一低或者一低一高

比如:1324   4231,再比如4213就是错的,因为4高,2低,接下来1就应该比2高,但是它没有

点击打开题目链接

接下来思路用笔记截图形式表示

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll maxn=;

ll dp[maxn][];

ll c[maxn][maxn];

int main()

{

    ll n;

    cin>>n;

    if(n==)

    {

        cout<<<<endl;

        return ;

    }

    c[][]=;

    for(ll i=;i<=n;i++)

        c[i][]=;

    for(ll i=;i<=n;i++)

        for(ll j=;j<=i;j++)

        {

            c[i][j]=c[i-][j]+c[i-][j-];

        }

    dp[][]=;dp[][]=;

    dp[][]=;dp[][]=;

    for(ll i=;i<=n;i++)

    {

        for(ll j=;j<=i-;j++)

        {

            dp[i][]+=c[i-][j]*dp[j][]*dp[i--j][];

        }

        dp[i][]/=;

        dp[i][]=dp[i][];

    }

    cout<<dp[n][]+dp[n][]<<endl;

    for(ll i=;i<=n;i++)

    {

        printf("\ni=%lld:%lld,%lld\n",i,dp[i][],dp[i][]);

    }

}