题意

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

思路

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

需要注意

c需要用long long去读
在计算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开始搜索。
在排序计数时退出条件应当是c == 1而不是c == 0。
然后注意是n - i + 1或者n - i（看下标上界是0还是1），不是i。