hdu3043Number game(dp+dfs)

题意：给你所有1-n的波浪型排列，输出按字典序将这些序列排序后第k小的数列。

思路：可以先预处理出第i个位置是j的上波浪方案数和下波浪方案数。对于每一位，从小到大枚举j，如果当前的总方案数刚好大于等于k，那么答案数列中这个位置一定是j，如此dfs找下去。

因为输入数据有很多的t，一直WA在这个地方，测数据时也发现数据不对劲，问学长要了数据才发现这个坑。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
const int N=25;
unsigned long long m,fu[N][N],fd[N][N];
int i,j,k,t,n;
int a[N];
void dfs(int d,long long k,int pre,int tp)
{
    if (d==0) return ;
    long long sum=0;
    int i;
    if (tp==-1)
    {
        for (i=1;i<pre;i++)
        {
            if (sum+fu[d][i]>=k) break;
            sum+=fu[d][i];
        }
    }
    else
    {
        for (i=pre;i<=d;i++)
        {
            if (sum+fd[d][i]>=k) break;
            sum+=fd[d][i];
        }
    }
    a[d]=i;
    dfs(d-1,k-sum,i,-tp);
}
int main()
{
    fd[1][1]=fu[1][1]=1;
    for (i=2;i<=20;i++)
    {
        for (j=1;j<=i;j++)
        {
            for (k=j;k<=i-1;k++) fu[i][j]+=fd[i-1][k];
            for (k=1;k<=j-1;k++) fd[i][j]+=fu[i-1][k];
        }
    }
    while(~scanf("%d",&t))
    	while(t--)
    {
    	scanf("%d%lld",&n,&m);
        if (n>250) n/=0;
        long long sum=0;
        for (i=1;i<=n;i++)
        {
            if (sum+fd[n][i]>=m)
            {
                a[n]=i;
                dfs(n-1,m-sum,i,-1);
                break;
            }
            sum+=fd[n][i];
            if (sum+fu[n][i]>=m)
            {
                a[n]=i;
                dfs(n-1,m-sum,i,1);
                break;
            }
            sum+=fu[n][i];
        }
        for (i=2;i<=n;i++)
            for (j=1;j<i;j++)
                if (a[i]<=a[j]) a[j]++;

        for (i=n;i>1;i--) printf("%d ",a[i]);
        printf("%d\n",a[1]);
    }
}