问题描述:

给你$n$块长度为$1-n$的木板,你需要将它们组成一个栅栏,并且在栅栏中木板是高低交错的(就是所有木板要么都比两边低,要么都比两边高)。

显然有很多构建栅栏都方案,于是给你一个整数$C$,你需要求出按照字典序排在第$C$个的构建方案。

输入:

第一行一个整数$K$,表示有$K$组数据
接下来$K$行每行两个整数$n, c$,表示一组数据($n<=20,c<=2^{63}$)

输出:

对于每组数据你需要输出字典序大小第$C$个第构建方案。

思路:

特别好的一道计数类DP。这题不光要你统计方案数,还要在它第基础上求出排名为$C$第方案。

我们设$f[i][j][k]$为:用$i$块木板,最左端木板从小大排在第$j$位,比两边都低($k=0$),或比两边都高($k=1$)的方案数。这个状态设计得十分精妙,不是直接设最左端木板的高度,而是设在$i$块木板中的排名。这样既方便了状态的转移,也方便了后面找方案的过程。

状态转移方程比较好推:$f[i][j][0]=\sum_{p=j}^{i-1}f[i-1][p][1]$和$f[i][j][1]=\sum_{p=1}^{j-1}f[i-1][p][0]$。这样我们就得出了方案数,接下来求排名为$C$的方案就比较容易了。我们从左到右枚举木板长度,比较方案数与排名的关系,进而推出答案。

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define MAXN 25
#define LL long long
using namespace std;

int T, n;
LL c, f[MAXN][MAXN][2];
bool vis[MAXN];

void init()
{
    f[1][1][0]=f[1][1][1]=1;
    for(int i=2; i<=20; i++)
        for(int j=1; j<=i; j++)
        {
            for(int k=1; k<j; k++) f[i][j][1]+=f[i-1][k][0];
            for(int k=j; k<i; k++) f[i][j][0]+=f[i-1][k][1];
        }
}

int main()
{
    init();
    scanf("%d", &T);
    while(T--)
    {
        int pos1, pos2;
        memset(vis, 0, sizeof(vis));
        scanf("%d%lld", &n, &c);

        for(int i=1; i<=n; i++)
        {
            if(f[n][i][1]>=c) {pos1=i, pos2=1; break;}
            else c-=f[n][i][1];
            if(f[n][i][0]>=c) {pos1=i, pos2=0; break;}
            else c-=f[n][i][0];
        }
        printf("%d ", pos1);
        vis[pos1]=1;

        for(int i=n-1; i>=1; i--)
        {
            int rank=0; pos2^=1;
            for(int j=1; j<=n; j++)
            {
                if(vis[j]) continue;
                rank++;
                if((pos2==0 && j>=pos1) || (pos2==1 && j<=pos1)) continue;
                if(f[i][rank][pos2]>=c)  {pos1=j; break;}
                else c-=f[i][rank][pos2];
            }
            printf("%d ", pos1);
            vis[pos1]=1;
        }
        printf("\n");
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注