POJ

题意：\(N(N<=20)\)块木板，长度分别为1,2,...,N，宽度都是1.把N块木板一高一低交错排好，显然会有多种方案，每个方案可以看做一个长度为N的序列，序列中各元素是木板的长度，按照字典序从小到大排序后，求第m个方案的具体方案，也就是输出第m个方案1到N各个木板的长度.

分析：设\(f[i][j][k]\)表示排好了i块木板，其中最左边的木板的长度在i块中从小到大排在第j位，且位置状况为k(k=0/1分别表示低位/高位).

\(f[i][j][0]=\sum_{k=j}^{i-1}f[i-1][k][1]\)这里解释一下为什么从j开始而不是j+1开始？因为我们这次新加入的木板在i块中排第j位，那么之前的i-1块木板中的第j位在i块木板中实际上是排到了第j+1位，也就是比这次填的要高，所以是合法的.

\(f[i][j][1]=\sum_{k=1}^{j-1}f[i-1][k][0]\)

我们预处理出f数组，然后采用数位DP中经常要用到的"试填法".我们首先单独确定第一块木板的高度和位置情况,记录变量last为上一块填入的木板的高度，k为上一块木板的位置情况.

从第2块木板开始，假设当前考虑第i块木板，记得每次k^=1求出这次填入的木板的位置情况,我们从小到大枚举长度len,该长度在剩余木板中排名为j，若当前k=0,则需要满足len<last,若k=1，则需要满足len>last.若\(f[n-i+1][j][k]<m\)，则令\(m-=f[n-i+1][j][k]\),继续尝试下一个j,若\(f[n-i+1][j][k]>=m\),更新last的值，第i块木板的长度就是len.

还有一些细节问题，见代码注释.

```cpp

include

include

include

include

include

include

include

define ll long long

using namespace std;
inline ll read(){
ll x=0,o=1;char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar();
if(ch==‘-‘)o=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)x=x10+ch-‘0‘,ch=getchar();
return xo;
}
const int N=25;
int visit[N];ll f[N][N][2];
inline void prework(){
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<=20;++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(){
prework();
int T=read();
while(T--){
memset(visit,0,sizeof(visit));
int n=read(),last,k;ll m=read();
for(int i=1;i<=n;++i){//考虑第一块木板
if(f[n][i][1]>=m){last=i;k=1;break;}
//一定要优先考虑f[n][i][1],因为我们要优先字典序最小,所以第一块k=1最好，则第二块是个低位
else m-=f[n][i][1];
if(f[n][i][0]>=m){last=i;k=0;break;}
else m-=f[n][i][0];
}
visit[last]=1;printf("%d",last);
for(int i=2;i<=n;++i){
k^=1;int j=0;
for(int len=1;len<=n;++len){
if(visit[len])continue;
++j;
if((k==0&&len<last)||(k==1&&len>last)){
if(f[n-i+1][j][k]>=m){last=len;break;}
else m-=f[n-i+1][j][k];
}
}
visit[last]=1;printf(" %d",last);
}
printf("\n");
}
return 0;
}

``

A decorative fence

原文：https://www.cnblogs.com/PPXppx/p/11255466.html