A decorative fence(POJ1037)

用长度从1至N的N块木板来围成一个围栏。要求是围栏成波浪形，即每块木板要么比它两边的木板都低（低位）要么比它两边的木板都高（高位)。现对所有符合要求的排列方式进行排序。排序规则是从第一块木板开始计算，越短的排名越前，前面的相等，向后依次比较。（即字典序）先给出N和一个指定的数字m，求符合要求的排列中的第m个。
输入：第一行一个正整数表示测试用例数。接下每行为一个测试用例，含两个数字分别表示N和m。
输出：指定的木板排列方案。 如图为n=4的所有情况
Sample Input
2
2 1
3 3                                                                       

Sample Output
1 2 
2 3 1

 

首先类似于倍增优化dp，我们用试填法确定排名为c的栅栏各木板长度。
我们首先可以枚举第1块木板的长度，设为h，后面n-1块木板构成的总方案数为t，
若t>=c，则说明第1块木板长就为h，继续尝试确定第2块木板长度，否则c-=t，h增加1，重复上述判断。
然则（如此那么）我们可以求出答案，现在我们需要预处理t的值

设f[i,j,k]表示用i块长度不同的木板构建栅栏，最左边的木板从小到大排第j位，其状态为k（k为0表示低位，k为1表示高位）

f[i,j,0]=∑p=j~i-1f[i-1,p,1]
f[i,j,1]=∑p=1~j-1f[i-1,p,0]

 

long long f[21][21][2],m; bool used[21]; void prepare() {int i,j,k;f[1][1][0]=f[1][1][1]=1;for(i=2;i<=20;i++)for(j=1;j<=i;j++){for(k=j;k<=i-1;k++)f[i][j][0]+=f[i-1][k][1];for(k=1;k<=j-1;k++)f[i][j][1]+=f[i-1][k][0];} }

 

接下来开始试填，记上一块木板长last，上一块高低位置为k，
1：k^=1;
2:枚举i的长度len，进行判断，找出确定的len
3：i加1，重复步骤

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; long long f[21][21][2],m; bool used[21]; void prepare() {int i,j,k;f[1][1][0]=f[1][1][1]=1;for(i=2;i<=20;i++)for(j=1;j<=i;j++){for(k=j;k<=i-1;k++)f[i][j][0]+=f[i-1][k][1];for(k=1;k<=j-1;k++)f[i][j][1]+=f[i-1][k][0];} } int main() {int t,n,i,j,k,last,len;scanf("%d",&t);prepare();while(t--){scanf("%d%lld",&n,&m);memset(used,0,sizeof(used));for(j=1;j<=n;j++)//第一块木板单独处理 {if(f[n][j][1]>=m){last=j;k=1;break;}else m-=f[n][j][1];if(f[n][j][0]>=m){last=j;k=0;break;}else m-=f[n][j][0];}used[last]=1;printf("%d ",last);for(i=2;i<=n;i++){k^=1;j=0;for(len=1;len<=n;len++){if(used[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];}}used[last]=1;printf("%d ",last);}puts("");}return 0; }

 

 

 

转载于:https://www.cnblogs.com/dsb-y/p/11200593.html

总结

以上是生活随笔为你收集整理的A decorative fence(POJ1037)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。