題目鏈接

A decorative fence Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 7513   Accepted: 2858 Description Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its PReface he already knew, what makes a little wooden fence cute. A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met: ?The planks have different lengths, namely 1, 2, . . . , N plank length units. ?Each plank with two neighbors is either larger than each of its neighbors or smaller than each of them. (Note that this makes the top of the fence alternately rise and fall.) It follows, that we may uniquely describe each cute fence with N planks as a permutation a1, . . . , aN of the numbers 1, . . . ,N such that (any i; 1 < i < N) (ai ? ai?1)*(ai ? ai+1) > 0 and vice versa, each such permutation describes a cute fence. It is obvious, that there are many di erent cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a1, . . . , aN) is in the catalogue before fence B (represented by b1, . . . , bN) if and only if there exists such i, that (any j < i) aj = bj and (ai < bi). (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbered (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number. After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he ordered, but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like. Input The first line of the input file contains the number K (1 <= K <= 100) of input data sets. K lines follow, each of them describes one input data set. Each of the following K lines contains two integers N and C (1 <= N <= 20), separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence. You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64-bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn抰 exceed the number of cute fences with N planks. Output For each input data set output one line, describing the C-th fence with N planks in the catalogue. More precisely, if the fence is described by the permutation a1, . . . , aN, then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces. Sample Input 22 13 3 Sample Output 1 22 3 1 Source CEOI 2002

題意：給定長度依次為1到n的木棒n個， 擺放規則為除了兩邊的木棒，剩下的木棒必須要比相鄰的兩個都高或者都低（即波浪形）。求按字典序從小到大排列的第c個序列。

題解：

參考思路

首先說說求指定編號問題的通法吧！

直接一位一位枚舉答案！枚舉一位時，計算在這樣的前綴下，后面的總的排列數。如果嚴格小于總編號，則該位偏小，換更大的數，同時更新總編號；若大于等于，則該位恰好，枚舉下一位，總編號不用更新。

先拋開此題，用最簡單的全排列問題來說明這種方法。如1，2，3，4的全排列，共有4！種，求第10個的排列是？

先試首位是1，后234有3！=6種<10,說明1偏小，轉化成以2開頭的第（10-6=4）個排列，而3！=6 >= 4，說明首位恰是2。

第二位先試1（1沒用過），后面2！=2個<4,1偏小，換成3（2用過了）為第二位，總編號也再減去2！，剩下2了。而此時2!>=2，說明第二位恰好是3。

第三位先試1，但后面1！<2，因此改用4。末位則是1了。

這樣得出，第10個排列是2-3-4-1。（從1計起）

這種方法的核心在于求，給定前綴下后面總的排列數。全排列問題較易求。同時還需記錄前面用過的數字。

再回到此題，同是這樣來求。但求后面總的排列數時，用到了遞推，或者說dp，不難的方程。

參考博客鏈接

用狀態方程dp[i][j][0]用來求在i個木棒中以第j短的木棒打頭且前兩根為升序的排列方案數， dp[i][j][1]用來求在i個木棒中以第j短的木棒打頭且前兩根為降序的排列方案數，詳細解釋在講義代碼的注釋里。

講義代碼：

#include <stdio.h>#include <string.h>#define UP 0#define DOWN 1#define maxn 25long long C[maxn][maxn][2];//C[i][k][DOWN] 是S(i)中以第k短的木棒打頭的DOWN方案數,C[i][k][UP] //是S(i)中以第k短的木棒打頭的UP方案數,第k短指i根中第k短void Init(int n){	memset(C, 0, sizeof(C));	C[1][1][UP] = C[1][1][DOWN] = 1;	int i, k, M, N;	for(i = 2; i <= n; ++i){		for(k = 1; k <= i; ++k){ //枚舉第一根木棒的長度			//枚舉第二根長度			for(M = k; M < i; ++M) C[i][k][UP] += C[i-1][M][DOWN];			//枚舉第二根長度			for(N = 1; N < k; ++N) C[i][k][DOWN] += C[i-1][N][UP];		}	}	//總方案數是 Sum{ C[n][k][DOWN] + C[n][k][UP] } k = 1.. n;}void Print(int n, long long cc){	long long skipped = 0, oldVal; //已經跳過的方案數	int seq[maxn]; //最終要輸出的答案	int used[maxn]; //木棒是否用過	memset(used, 0, sizeof(used));	for(int i = 1, k; i <= n; ++i){ //依次確定位置i的木棒序號		int No = 0;		for(k = 1; k <= n; ++k){ //枚舉位置i的木棒			oldVal = skipped;			if(!used[k]){				++No; //k是剩下木棒里的第No短的				if(i == 1) skipped += C[n][No][UP] + C[n][No][DOWN];				//以下尋找合法位置				else if(k > seq[i-1] && (i == 2 || seq[i-2] > seq[i-1]))					skipped += C[n-i+1][No][DOWN];				else if(k < seq[i-1] && (i == 2 || seq[i-2] < seq[i-1]))					skipped += C[n-i+1][No][UP];				if(skipped >= cc) break;			}		}		used[k] = 1;		seq[i] = k;		skipped = oldVal;	}	for(int i = 1; i <= n; ++i)		if(i < n) printf("%d ", seq[i]);		else printf("%d/n", seq[i]);}int main(){	int T, n; long long c;	Init(20);	scanf("%d", &T);	while(T--){		scanf("%d%lld", &n, &c);		Print(n, c);	}	return 0;}
自己的代碼：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=20+10;ll d[maxn][maxn][2];//up-0 down-1void init(){    memset(d,0,sizeof(d));    d[1][1][0]=d[1][1][1]=1;    rep(i,2,21)    {        rep(j,1,i+1)        {            rep(x,1,j)            d[i][j][1]+=d[i-1][x][0];            rep(x,j,i)            d[i][j][0]+=d[i-1][x][1];        }    }}int ans[maxn],used[maxn];void solve(int n,ll c){    memset(ans,0,sizeof(ans));    memset(used,0,sizeof(used));    ll sum=0,t=0;    rep(i,1,n+1)    {        int num=0;        rep(k,1,n+1)        {            t=sum;            if(!used[k])            {                num++;                if(i==1)                    sum+=d[n][num][0]+d[n][num][1];                else if(i==2)                {                    if(k>ans[1])                        sum+=d[n-i+1][num][1];                    else                        sum+=d[n-i+1][num][0];                }                else                {                    if(k>ans[i-1]&&ans[i-1]<ans[i-2])                        sum+=d[n-i+1][num][1];                    if(k<ans[i-1]&&ans[i-1]>ans[i-2])                        sum+=d[n-i+1][num][0];                }                if(sum>=c)                {                    used[k]=1;                    ans[i]=k;                    break;                }            }        }        sum=t;    }    rep(i,1,n+1)    printf("%d%c",ans[i],i==n?'/n':' ');}int main(){    init();    int cas;    scanf("%d",&cas);    while(cas--)    {        int n;        ll c;        scanf("%d%lld",&n,&c);        solve(n,c);    }    return 0;}