POJ 1037 A decorative fence DP

这题挺复杂的。

设dp[i][k][0/1]表示 i个木棍,第k小在第一个,为波峰型/波谷型的方案数。

这个转移倒十分显然。

dp[i][k][0] = sum(dp[i – 1][k -> i][1])

dp[i][k][1] = sum(dp[i – 1][1 -> k][0])

边界为dp[1][1][0] = dp[1][1][1] = 1。

考虑 一下这个DP转移的正确性。

每次我们考虑一个长度为i的序列。我们假设我们新加入的是i。然后我们枚举一个i属于这个序列中的第几大,然后我们去维护对应的方案,显然是正确的。

求出这个DP数组后我们依旧无法求解。我们先考虑一个单纯的排列,求其字典序第k个。显然我们一位一位考虑,如果这一位选i,产生的新方案数小于k,我们就认为这意味是>=i的。然后我们就可以求解出第K个方案数。

然后我们考虑这道题如何使用类似的思想求出第K个方案。

我们先明确以下事实。

当我求第i位的时候,第i-1位已经确定。

我们可以明确的求出,某一位取i,这一位在剩下为使用的数中的大小排名。

我们依旧按位考虑。

对于每一位,我们依次考虑1->n个数,如果这个数没有被使用,那么我们看一下,他会造成多少新方案(由于我们已经知道这个数在剩下数中的排名,所以可以知道方案数。),如果发现新方案超过k了,那么显然这一位就是这个数。否则k减去产生的方案数。然后这里有一些细节需要注意,比如考虑波峰波谷不单考虑i和i-1的关系,还要考虑i-2的关系。波谷和波峰间要优先考虑波谷,因为i相同,排名边界相同波谷的方案字典序全部小于波峰方案。

发表评论