用長度從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)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。