poj1037 A decorative fence<DP>

题意:

有N条木板，长度不同，分别为1，2，……，N单位长度。现在要将这N条木板排成不在边缘的木板，两边相邻的木板要么都比它高，要么都比它低，成波浪形排列。

现将这些排列按字典排序，即第一条木板较短的排前面，若第一条木板相同，则第二条木板相同的排前面，以此类推；最后，从1开始对排列方法编号。

现输入木板条数N和编号C，要求按顺序输出这N条木板的长度（长度分别为1到N）;

思路:

DP方程, 即 DP.down[i][l] 表示以 i 开始，长度为 l，并且初始初始状态是向下放置的（即第二个数小于第一个数），DP.up[i][][l] 同理，那么就有
DP.down[i][l] = sigema{DP up[[k][l-1](1<=k<i)}
DP.up[i][l] = sigema{DP.down[l+1-i][l].

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 typedef long long LL;
 9 
10 int T, N, j;
11 LL M, dp[21][21][2], C;
12 bool mark[22], f;
13 void Init( )
14 {
15     dp[1][1][0]=dp[1][1][1]=1;
16     for (int len=2;len<=20;len++)   
17     for (int i=1;i<=len;i++){  
18         for (int j=1;j<i;j++) dp[len][i][0]+=dp[len-1][j][1];  
19         for (int j=i;j<len;j++) dp[len][i][1]+=dp[len-1][j][0];  
20     }  
21 } 
22 
23 
24 int main( )
25 {
26     Init( );
27     scanf("%d", &T);
28     while( T-- ){
29         scanf( "%d%lld", &N, &M );
30         memset(mark,0,sizeof(mark));
31         int l=1, r=N;
32         f=false, C=M;
33         for( int i=1; i<=N && !f; ++ i ){  // 求第一快 
34             for( j=0; j<2; ++ j ){
35                 C-=dp[N][i][j];
36                 if( C<=0 ){
37                     C+=dp[N][i][j];
38                     mark[i]=1;
39                     printf( "%d", i );
40                     f=true;
41                     if( j==0 )l=1, r=i-1;
42                     else l=i+1, r=N;
43                     j^=1;// 换方向 
44                     break;
45                 }
46             }    
47         }
48         for( int i=N-1; i>=1; --i ){// 剩下的 
49             int t=0;
50             for( int k=1; k<l; ++ k )
51                 if( !mark[k] )t++;
52             for( int k=l; k<=r; ++ k ){
53                 if( !mark[k] ){
54                     t++;
55                     C-=dp[i][t][j];
56                     if( C<=0 ){
57                         C+=dp[i][t][j];
58                         mark[k]=1;
59                         printf( " %d", k );
60                         if( j==0 ) l=1, r=k-1;
61                         else l=k+1, r=N;
62                         j^=1; 
63                         break;    
64                     }
65                 }
66             }
67         }
68         puts( "" );    
69     }
70     return 0;
71 }