解题报告
题目来源：
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个木条构成的栅栏是美观的，那么它必须具备两个条件：1、n个木条必须具有不同的长度；2、与任一木条相邻的两个木条，它们的高度既不会都比中间的木条高，也不会都比中间的木条低。（也就是说栅栏呈“波浪”型排列）由n个木条构成的栅栏，可以有多种排列方式。为了区分这些排列方式，还定义了排列方式之间的大小关系。假设一种排列方式为a（a1,a2,a3…an），另一种排列方式为b（b1,b2,b3…bn），a<b当且仅当存在i使得，对于任意j<i，aj=bj，且ai<bi。（其实就是字典顺序。）现在给你木条数n和c，n个木条构成的栅栏，排列顺序从小到大排列，问你第c中排列的顺序是什么。
题目分析与算法模型
通过分析可以知道，木条的具体长度是多少并不重要，只要满足木条之间的长度不相等就可以了。为了简单起见，就设n根木条的长度从小到大依次为1～n。先从n比较小的情况找找规律，比如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。可以看出，当第一位数字X已经确定时，X后面的数字一定是先从1～X-1开始考虑（比X低的那些木条），然后再从X+1到n考虑（比X高的那些木条）。其实，我们可以把排列方式分为两种，一种是第一个木条比第二个木条高的排列方式，我们简记为W方式；另一种是第一个木条比第二个木条低的排列方式，我们简记为M方式。当第一个数字确定时，我们总是首先考虑所有W方式，等W方式全部考虑完，再去考虑所有的M方式。那么，n个木条的排列顺序就为：
W1 （以第一根木条开始的W排列方式）
M1 （以第一根木条开始的M排列方式）
W2 （…）
M2
…
Wn
Mn
假设我们可以知道每一种排列方式的种类，那么我们就可以判断出我们要求的第c种排列方式落在了上述的哪个区间，这样我们就可以把第一根木条确定下来。规模较小到了1～n-1，若木条落在W方式下，我们就找下一个的M方式；若木条是落下M方式，我们就找下一个的W方式，用同样的方法确定第二根木条，然后以此类推，求出所有的木条，问题就可以解决了！但是别急，貌似其中还有一些问题。当我们确定了一根木条，去找第二根木条时，剩下的木条的长度就是不连续的了，子问题与原问题是同一类问题吗？其实不用担心，原问题是1～n个长度不同的木条以M或者W方式排列的个数，我们只是为了方便记录状态，而将他们的长度规定为1～n，即使它们的长度是不连续的，问题的本质还是一样的。我们可以这样想：我们在第一步确定了1～n个木条中的第x个，那么我们在寻找下一根木条时，事先可以将（x+1）～n的木条长度减1，这样长度就变成了长度为1～（n-1）的n-1根木条的排列问题了。
我们可以设M[x][n]为由n个长度不同的木条组成的栅栏中，以其中第x根木条开始的“M”型排列的个数，W[x][n]为由n个长度不同的木条组成的栅栏中，以其中第x根木条开始的“W”型排列的个数。可以推出以下公式：
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根是对应的)
这样确定了状态和状态转移，只要事先进行预处理，计算出W和M，就可以一步步推算出区间，最终算出第c个排列的情况。这里要注意：在查找第一根木条时，既要考虑W方式，又要考虑M方式。而在已找到是在W（或M）方式的区间的时候，就只能考虑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范围内第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做时，不妨先想出一个可以表示问题的状态，再看是否可以根据题中的所描述的操作进行状态转移，并且看转移之后的状态是否是假设出的状态，即看自己假设出的表示问题的状态是否具有最优子结构。若没有，则应该假设另一种状态或者在原先状态的基础上进行修改和加强，直到找出符合最优子结构的状态。