POJ 1037 A Decorative Fence 动态规划解排序计数

这是在北京大学暑期课《ACM/ICPC竞赛训练》的一道DP的题目。

题意

现在要排列长度为[1..N]的N个木棒,要求除了两端的木棒外,每一根木棒要不比左右的都长,要不比左右的都短。现在给定C,要求输出在所有符合上述条件的建法中按照字典序第C种排布方式。

思路

这是课程pdf提供的源码(修改后)


这是我的代码
这道题分成两步,第一步是计算合法排列数量N,第二步是通过N来计算第C个合法排列。
第一步,其实可以先写一个递归的方案,然后再改成dp就行了,我觉得比较巧妙的地方是把up方案和down方案区分开来了。
第二步,依次对第[1..i]位枚举剩下来的第[1..k]长的木棒,因为已经求得up[i][k]down[i][k]
这种思想可以用来实现C++里面的next_permutation函数,这里给出了一个实现

需要注意

  1. c需要用long long去读
  2. 在计算up[i][k]的时候,我原先是从k + 1开始算的,但是实际上应当从k开始算。因为up[i][k]指的是所有由i个木棒组成的方案中以这些木棒中第k短的木棒开头的up方案的个数。也就是需要取走第k短木棒kk后的i - 1木棒组成的是一个down方案。注意到取走kk后,应当从比kk长的第一个木棒开始计算,也就是从i根木棒的第k + 1短开始。但是原来i根木棒的第k + 1短变成了现在i - 1根木棒的第k短,因此还是要从k开始搜索。
  3. 在排序计数时退出条件应当是c == 1而不是c == 0
  4. 然后注意是n - i + 1或者n - i(看下标上界是0还是1),不是i