POJ1037A decorative fence(动态规划+排序计数+好题）

题意：输入木棒的个数n，其中每个木棒长度等于对应的编号，把木棒按照波浪形排序，然后输出第c个;

分析：总数为i跟木棒中第k短的木棒就等于总数为i-1中比这一根短的方案数 + 和比这一根长的方案数；最后用一个三维数组表示成c[i][k][up/down],c[i][k][up]表示i跟木棒中第k短的下一个比他长的方案数，就可以枚举每一个比他长的数相加；

排列计数问题：求一个排列中第几个是什么？

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define UP 0
 8 #define DOWN 1
 9 const int MAX = 30;
10 long long c[MAX][MAX][2];
11 int seq[MAX],used[MAX];
12 void Init(int n)
13 {
14     memset(c, 0, sizeof(c));
15     c[1][1][UP] = c[1][1][DOWN] = 1;
16     for(int i = 2; i <= n; i++)  //个数
17     {
18         for(int k = 1; k <= i; k++)  //第i短
19         {
20             for(int N = k; N < i; N++)
21             {
22                 //这个循环为什么k而不是k+1开始呢？
23                 //因为c[i][k][UP]是指以i个木棒中第k短开头的上升木棒,那么下一个的总数就是i-1,那是i-1中第几短呢，除掉前面的那个k，比他长的就是第k到i-1（除去k后，比他稍微长点的就成了第k短）
24                 c[i][k][UP] +=  c[i - 1][N][DOWN];
25             }
26             for(int M = 1; M <= k - 1; M++)
27             {
28                 //这个没啥影响
29                 c[i][k][DOWN] += c[i - 1][M][UP];
30             }
31         }
32     }
33 }
34 void print(int n, long long cc)
35 {
36     long long  skipped = 0;
37     int No = 0;
38     long long  oldValue = skipped;
39     memset(used, 0, sizeof(used));
40     for(int i = 1; i <= n; i++)
41     {
42         int k;
43         No = 0;
44         oldValue = skipped;
45         for(k = 1; k <= n; k++)
46         {
47             oldValue = skipped;//用oldvalue保留每一次最先开始的次数，然后skipped不断算跳跃的方案数
48             if(used[k] == 0)
49             {
50                 No++;
51                 if(i == 1)
52                 {
53                     skipped += c[n][No][UP] + c[n][No][DOWN];
54                 }
55                 else
56                 {
57                     if(k > seq[i - 1] && (i <= 2 || seq[i - 2] > seq[i - 1]))
58                     {
59                         skipped += c[n - i + 1][No][DOWN];
60                     }
61                     else if(k < seq[i - 1] && (i <= 2 || seq[i - 2] < seq[i - 1]))
62                     {
63                         skipped += c[n - i + 1][No][UP];
64                     }
65                 }
66                 if(skipped >= cc) //跳跃的方案数比给定的大，那就跳出循环，如果比cc小就在改变oldvalue值
67                     break;
68             }
69         }
70         used[k] = true;
71         seq[i] = k;
72         skipped = oldValue;
73     }
74     for(int i = 1; i < n; i++)
75         printf("%d ", seq[i]);
76     printf("%d
", seq[n]);
77 }
78 int main()
79 {
80     int t,n;
81     long long C;
82     Init(20);
83     scanf("%d", &t);
84     while(t--)
85     {
86         scanf("%d%I64d", &n,&C);
87         print(n, C);
88     }
89     return 0;
90 }

View Code