hdu4489 组合公式+dp

这里对于题意在说明一下, 题目中要求的排列必须是波浪形,每一个在排列中的人不是波峰就是波谷,如果它既不是波峰也不是波谷排列就是错的.

对于我这种数学渣渣来说,做一道dp题要好久,%>_<% 怎么想到的DP呢? 首先他看起来像搜素,但数据范围很大(对于深搜来说20就够大了),抱着试一试的心态用暴搜写了一下,结果在n=12是爆掉了,怎么优化慢了一倍的时间呢? 由于我剪枝能力一点都不高,然后我觉得搜素爆掉就要想dp,然后越想越觉得很对.

解题思路,假设n个人身高从1到n升序排列,我们先把题目分解成一个最小子问题,就是第n个人要插在哪里? 他前面有n-1人, 那么就有n个孔等着他插,假设他插到了第j个位置,前面有j-1人,后面有n-j人. 那么第一个式子就出来了,当第n个人在j位置时,对于这种情况的排列总数为前面j-1人的总排列数*后面n-j人的总排列数,这是不是就是很明显的dp了,求一个解必须已知其他的解,但现在其他的解没有规律无法求出,那么就找出规律来. 咱们在想,第n个人是不是一定最高,他插在j位置,他前面的那个人一定比他矮,那么第n个人前面的那个序列最后两人一定是降序排列的,我们设这种状态为0,那后面的那个序列的前面两人也一定是升序排列的,我们设为1,那么此时有dp[j][0]代表j个人最后两人是升序排列的总排列数,dp[n-j][1]代表n-j个人最前面两人是升序排列的.但是还没完,还有很重要的一点没有考虑到, 第n个人前面的j-1个人是不是不知道选谁,因为第n个人在最初排列中他前面有n-1个人这n-1中选哪几个站在第n个人前面呢? 不要考虑身高(因为对于波浪线来说总会有合适的) 这样是不是c(n-1,j-1)一下,前面的人确定了,后面的人也就随之确定了,所以就不用考虑了.

这样推到之后,有递推公式 c(n-1,j-1)*dp[j-1][0]*dp[n-j][1] 由于对称性 sum[n](n的总排列数)/2=dp[n][0]=dp[n][1],想一想对不对?

那么最终n的总排列数就等于把所有孔算完相加的值,代码如下.

#include<cstdio>
#include<cstring>

using namespace std;

__int64 dp[21][2];
__int64 answer[21];

__int64 C(int x,int y)  //   xÊÇµ×Êý
{
    __int64 mother=1,son=1;
    for(int i=0;i<y;i++)
    {
        mother*=(y-i);
        son*=(x-i);
    }
    return son/mother;
}
int main()
{
    for(int i=0;i<=20;i++){
        for(int j=0;j<2;j++)
            dp[i][j]=1;
    }
    answer[1]=1;
    for(int i=2;i<=20;i++){
        for(int j=1;j<=i;j++){
            answer[i]+=C(i-1,j-1)*dp[j-1][0]*dp[i-j][1];

        }
        dp[i][0]=dp[i][1]=answer[i]/2;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int k,n;
        scanf("%d%d",&k,&n);
        printf("%d ",k);
        printf("%I64d
",answer[n]);
    }
    return 0;
}