【题解】P7690 [CEOI2002] A decorative fence

yaoxiangyuan · 2022-01-02 10:17:28 · 题解

修改于2022 2.28,感觉之前写的很不好，于是修改一下。

题目链接

1.题意

有 N 块长方形的木板，长度分别为 1, 2 ,…,N，宽度都是 1 。

现在要用这 N 块木板组成一个宽度为 N 的围栏，满足在围栏中，每块木板两侧的木板要么都比它高，要么都比它低。

也就是说，围栏中的木板是高低交错的。

我们称“两侧比它低的木板”处于高位，“两侧比它高的木板”处于低位。

显然，有很多种构建围栏的方案。

每个方案可以写作一个长度为 N 的序列，序列中的各元素是木板的长度。

把这些序列按照字典序排序,给定整数 C ,求排名为 C 的围栏中，各木板的长度从左到右依次是多少。

2.知识点前置

计数 dp ,还有类似于康托展开的思想。

①动态规划不仅对于求解最优解问题有效，还可以用来求解各种排列组合的个数、概率或者期望之类的计算。而计数 dp 便有这个功能。

②一般的康托展开可以用来求一个 1 到 n 的任意排列的排名。

3.解题思路

只考虑最左边的一位 x 应该是多少?

如果第一位 x=h , 后面的 N-1 个空构成的方案数为 T_{1} \geq C ，那么第一位就应该是 h 。

否则, 第一位 x=x+1, C=C-T_{1} , 再次重复考虑

复杂一点的话, 有一道例题需要与处理, 问题是一个位还分为 高位, 低位, 高位和低位要进行状态编码, 0 表示低位, 1 表示高位

4.代码

#include<bits/stdc++.h>
using namespace std;
int T,n;
long long m,f[25][25][5];
bool pd[25];
void csh(){
    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=j;k<=i-1;k++){
                f[i][j][0]+=f[i-1][k][1];
            }
            for(int k=1;k<=j-1;k++){
                f[i][j][1]+=f[i-1][k][0];
            }
        }
    }
}
int main(){
    csh();
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&m);
        memset(pd,0,sizeof(pd));
        int las,kk;
        for(int j=1;j<=n;j++){
            if(f[n][j][1]>=m){
                las=j;
                kk=1;
                break;
            }else{
                m-=f[n][j][1];
            }
            if(f[n][j][0]>=m){
                las=j;
                kk=0;
                break;
            }else{
                m-=f[n][j][0];
            }
        }
        printf("%d",las);
        pd[las]=1;
        for(int j=2;j<=n;j++){
            kk^=1;
            int pm=0;
            for(int l=1;l<=n;l++){
                if(pd[l]){
                    continue;
                }
                pm++;
                if(kk==0&&l<las||kk==1&&l>las){
                    if(f[n-j+1][pm][kk]>=m){
                        las=l;
                        break;
                    }else{
                        m-=f[n-j+1][pm][kk];
                    }
                }
            }
            pd[las]=1;
            printf(" %d",las);
        }
        puts("");
    }
    return 0;
}