首页 > 代码库 > POJ 1037 (计数 + DP) 一个美妙的栅栏

POJ 1037 (计数 + DP) 一个美妙的栅栏

2024-07-22 01:03:28   215人阅读

这道题总算勉勉强强看懂了，DP和计数都很不好想

DP部分：

称i根木棒的合法方案集合为S(i)，第二根木棒比第一根长的方案称作UP方案，反之叫做DOWN方案

C[i][k][DOWN] 是S(i)中以第k短(而不是长度为k)的木棒打头的DOWN方案数。

假设S(i)中第一根木棒长为x，那么构成合法的方案数有两类：

  1. S(i - 1)中第一根木棒比x长的DOWN方案
  2. S(i - 1)中第一根木棒比x短的UP方案

有如下递推关系：

C[i][k][UP] = ∑ C[i-1][M][DOWN]
M = k ... i -1
C[i][k][DOWN] = ∑ C[i-1][N][UP]
N = 1… k-1

举个例子：

比如四根木棒，假设第一根木棒长度为2，在剩下的1 3 4中，比2长的3和4分别是S(3)中第2和第3短的。(要和C所定义的状态相对应)

所以上式的M和N的范围就是这样的

总的方案数就是：Sum{ C[n][k][DOWN] + C[n][k][UP] } k = 1.. n

 

计数部分：

扔掉这个题，考虑一下这个问题：

1 2 3 4全排列，求字典序的第10个

首先假设第一个数是1，那么后面有3! = 6 < 10种排列情况，所以打头的不是1。  继续假设是2，后面三个数也有6种排列情况， 6 + 6 ≥ 10，所以第一个数确定是2，此时跳过了第一个数为1的6种情况。

继续假设第二个数是1，后面有2! = 2种情况， 2 + 6 ＜ 10，所以假设第二个数是3(注意2已经在第一个数中用过了)，依旧是有2种情况， 8 + 2 ≥ 10，第二个数确定是3，跳过了10种情况。

后面因为10 ≥ 10，所以第三第四个数分别是1 4

所求的排列就是2 3 1 4

 

回到这个题上来：

前面已经求得了i个数中第k小打头的方案数，所以我们也完全可以模拟上面的思维过程来求解。

微调：以第i短的木棒作第k根时，有UP和DOWN两类方案，先用DOWN的方案数和C比较

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 25; 8 const int UP = 0; 9 const int DOWN = 1;10 long long C[maxn][maxn][2];11 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         for(int k = 1; k <= i; ++k)18         {19             for(int M = k; M < i; ++M)20                 C[i][k][UP] += C[i - 1][M][DOWN];21             for(int N = 1; N <= k - 1; ++N)22                 C[i][k][DOWN] += C[i - 1][N][UP];23         }24 }25 26 void Print(int n, long long c)27 {28     long long skipped = 0;29     int seq[maxn], used[maxn];30     memset(used, 0, sizeof(used));31     for(int i = 1; i <= n; ++i)32     {33         long long oldVal = skipped;34         int k, No = 0;35         for(k = 1; k <= n; ++k)36         {37             oldVal = skipped;38             if(!used[k])39             {40                 ++No;41                 if(i == 1)42                     skipped += C[n][No][UP] + C[n][No][DOWN];43                 else44                 {45                     if(k > seq[i - 1] && (i == 2 || seq[i - 2] > seq[i - 1]))46                         skipped += C[n - i + 1][No][DOWN];47                     else if(k < seq[i - 1] && (i == 2 || seq[i - 2] < seq[i - 1]))48                         skipped += C[n - i + 1][No][UP];49                 }50                 if(skipped >= c)51                     break;52             }53         }54         used[k] = 1;55         seq[i] = k;56         skipped = oldVal;57     }58 59     for(int i = 1; i < n; ++i)    printf("%d ", seq[i]);60     printf("%d\n", seq[n]);61 }62 63 int main(void)64 {65     #ifdef LOCAL66         freopen("1037in.txt", "r", stdin);67     #endif68 69     int T, n;70     long long c;71     Init(20);72     scanf("%d", &T);73     while(T--)74     {75         scanf("%d %lld", &n, &c);76         Print(n, c);77     }78     return 0;79 }
代码君

 

POJ 1037 (计数 + DP) 一个美妙的栅栏


联系
我们