hdu4489（递推dp）

时间：2024-10-01 10:03:20

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4489

题意：给一个n,求n个高矮不同的人排成一排使得高、矮依次排列的种数。

详细思路参考：http://blog.****.net/bossup/article/details/9915647

这类题都是独立出最后一个再分情况讨论如何排进去。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 0x3f3f3f3f

#define N 1000010

#define clr(a) (memset(a,0,sizeof(a)))

using namespace std;

LL dp[][],ans[],c[][];

void init()

{

    for(int i=;i<=;i++)c[i][]=c[i][i]=;

    for(int i=;i<=;i++)

        for(int j=;j<i;j++)c[i][j]=c[i-][j-]+c[i-][j];

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

    for(int i=;i<=;i++)

    {

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

        {

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

        }

        dp[i][]=dp[i][]=ans[i]/;

    }

}

int main()

{

    int t,cas,n;init();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&cas,&n);

        printf("%d %I64d\n",cas,ans[n]);

    }

}

相关文章