解題報告
題目來源：
PKU 1037 A decorative fence
分類：
DP
原文：
A decorative fence
|
Time Limit: 1000MS
|
|
Memory Limit: 10000K
|
|
Total Submissions: 2051
|
|
Accepted: 608
|
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
2
2
1
3
3
Sample Output
1
2
2
3 1
Source
CEOI
2002
中文描述：
首先告訴你，如果一個由n個木條構(gòu)成的柵欄是美觀的，那么它必須具備兩個條件：1、n個木條必須具有不同的長度；2、與任一木條相鄰的兩個木條，它們的高度既不會都比中間的木條高，也不會都比中間的木條低。（也就是說柵欄呈“波浪”型排列）由n個木條構(gòu)成的柵欄，可以有多種排列方式。為了區(qū)分這些排列方式，還定義了排列方式之間的大小關(guān)系。假設一種排列方式為a（a1,a2,a3…an），另一種排列方式為b（b1,b2,b3…bn），a<b當且僅當存在i使得，對于任意j<i，aj=bj，且ai<bi。（其實就是字典順序。）現(xiàn)在給你木條數(shù)n和c，n個木條構(gòu)成的柵欄，排列順序從小到大排列，問你第c中排列的順序是什么。
題目分析與算法模型
通過分析可以知道，木條的具體長度是多少并不重要，只要滿足木條之間的長度不相等就可以了。為了簡單起見，就設n根木條的長度從小到大依次為1～n。先從n比較小的情況找找規(guī)律，比如n=4，那么排列順序為：1 3 2 4、1 4 2 3、2 1 4 3、2 3 1 4、2 4 1 3、3 1 4 2、3 2 4 1、3 4 1 2、4 1 3 2、4 2 3 1。可以看出，當?shù)谝晃粩?shù)字X已經(jīng)確定時，X后面的數(shù)字一定是先從1～X-1開始考慮（比X低的那些木條），然后再從X+1到n考慮（比X高的那些木條）。其實，我們可以把排列方式分為兩種，一種是第一個木條比第二個木條高的排列方式，我們簡記為W方式；另一種是第一個木條比第二個木條低的排列方式，我們簡記為M方式。當?shù)谝粋€數(shù)字確定時，我們總是首先考慮所有W方式，等W方式全部考慮完，再去考慮所有的M方式。那么，n個木條的排列順序就為：
W1 （以第一根木條開始的W排列方式）
M1 （以第一根木條開始的M排列方式）
W2 （…）
M2
…
Wn
Mn
假設我們可以知道每一種排列方式的種類，那么我們就可以判斷出我們要求的第c種排列方式落在了上述的哪個區(qū)間，這樣我們就可以把第一根木條確定下來。規(guī)模較小到了1～n-1，若木條落在W方式下，我們就找下一個的M方式；若木條是落下M方式，我們就找下一個的W方式，用同樣的方法確定第二根木條，然后以此類推，求出所有的木條，問題就可以解決了！但是別急，貌似其中還有一些問題。當我們確定了一根木條，去找第二根木條時，剩下的木條的長度就是不連續(xù)的了，子問題與原問題是同一類問題嗎？其實不用擔心，原問題是1～n個長度不同的木條以M或者W方式排列的個數(shù)，我們只是為了方便記錄狀態(tài)，而將他們的長度規(guī)定為1～n，即使它們的長度是不連續(xù)的，問題的本質(zhì)還是一樣的。我們可以這樣想：我們在第一步確定了1～n個木條中的第x個，那么我們在尋找下一根木條時，事先可以將（x+1）～n的木條長度減1，這樣長度就變成了長度為1～（n-1）的n-1根木條的排列問題了。
我們可以設M[x][n]為由n個長度不同的木條組成的柵欄中，以其中第x根木條開始的“M”型排列的個數(shù)，W[x][n]為由n個長度不同的木條組成的柵欄中，以其中第x根木條開始的“W”型排列的個數(shù)。可以推出以下公式：
M[x][n] = ∑W[i][n-1] (1<=i<=x-1)
W[x][n] = ∑M[i][n-1] (x<=i<=n-1)
M[x][n] = W[n-x+1][n] (長度從小到大排列的木條，第x根與第n-x+1根是對應的)
這樣確定了狀態(tài)和狀態(tài)轉(zhuǎn)移，只要事先進行預處理，計算出W和M，就可以一步步推算出區(qū)間，最終算出第c個排列的情況。這里要注意：在查找第一根木條時，既要考慮W方式，又要考慮M方式。而在已找到是在W（或M）方式的區(qū)間的時候，就只能考慮M（或W）方式了。
代碼：
#include <iostream>
using namespace std;
const int MAX = 21;
__int64 W[MAX][MAX];
__int64 M[MAX][MAX];
int used[MAX]; //用于輸出時判斷木條的使用情況
__int64 c;
int n;
void Input ()
{
scanf("%d%I64d", &n, &c);
}
//利用遞歸進行初始化
__int64 getDown (int x, int n);
__int64 getUp (int x, int n);
__int64 getDown (int x, int n)
{
if ( W[x][n] != -1 )
return W[x][n];
int i;
__int64 ans;
ans = 0;
for (i=1; i<x; i++)
ans += getUp (i, n-1);
return ( W[x][n] = ans );
}
__int64 getUp (int x, int n)
{
if ( M[x][n] != -1 )
return M[x][n];
return ( M[x][n] = getDown(n-x+1, n) );
}
void Init ()
{
int i, j;
memset(W, -1, sizeof(W));
memset(M, -1, sizeof(M));
for (i=1; i<=MAX; i++)
W[1][i] = 0;
W[1][1] = 1;
M[1][1] = 1;
W[1][2] = 0;
M[1][2] = 1;
W[2][2] = 1;
M[2][2] = 0;
for (i=3; i<=MAX; i++)
{
for (j=1; j<=i; j++)
{
getDown(j, i);
getUp(j, i);
}
}
}
//子問題中，1～k范圍內(nèi)第x根木條實際的位置
void Output (int x, int k)
{
int i;
do
{
for (i=1; i<=k; i++)
{
//若1～k中有以前已確定的木條，并且x木條比已確定的木
//條長度要長，那么x木條的長度應加1
if ( used[i] && x >= i )
{
x++;
k++;
}
}
} while ( used[x] );
if ( k > 1 )
printf("%d ", x);
else
printf("%d", x);
used[x] = 1;
}
void Solve ()
{
int up, i, first;
up = 1;
i = 1;
first = 1;
memset(used, 0, sizeof(used));
while ( n > 0 )
{
if ( up == 1 )
{
if ( c > M[i][n] )
{
if ( first ) //是否是在查找第1根木條
{
up = !up;
}
c -= M[i][n];
i++;
}
else
{
Output(i, n);
first = 0;
up = !up;
n--;
}
}
else
{
if ( c > W[i][n] )
{
if ( first )
{
up = !up;
}
c -= W[i][n];
if ( !first )
{
i ++;
}
}
else
{
Output(i, n);
first = 0;
up = !up;
n--;
i = 1;
}
}
}
printf("\n");
}
int main ()
{
int test;
cin>>test;
Init ();
while ( test-- )
{
Input ();
Solve ();
}
return 0;
}
心得：
當預感到一道題目可以用DP做時，不妨先想出一個可以表示問題的狀態(tài)，再看是否可以根據(jù)題中的所描述的操作進行狀態(tài)轉(zhuǎn)移，并且看轉(zhuǎn)移之后的狀態(tài)是否是假設出的狀態(tài)，即看自己假設出的表示問題的狀態(tài)是否具有最優(yōu)子結(jié)構(gòu)。若沒有，則應該假設另一種狀態(tài)或者在原先狀態(tài)的基礎(chǔ)上進行修改和加強，直到找出符合最優(yōu)子結(jié)構(gòu)的狀態(tài)。