动态规划03

今天主要讨论如何解决高维的动态规划问题，即很难直接想出来递推关系。

美妙的栅栏

Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute. A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met:

• The planks have different lengths, namely 1, 2, . . . , N plank length units.

• Each plank with two neighbors is either larger than each of its neighbors or smaller than each of them. (Note that this makes the top of the fence alternately rise and fall.)
  

  It follows, that we may uniquely describe each cute fence with N planks as a permutation a1, . . . , aN of the numbers 1, . . . ,N such that (any i; 1 < i < N) (ai − ai−1)*(ai − ai+1) > 0 and vice versa, each such permutation describes a cute fence. It is obvious, that there are many di�erent cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a1, . . . , aN) is in the catalogue before fence B (represented by b1, . . . , bN) if and only if there exists such i, that (any j < i) aj = bj and (ai < bi). (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbered (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.
  After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he ordered, but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like.
  

    题目就很长，但大致意思很容易：我们要找一个满足以下性质的排列：

• 排列里的数字满足波浪形；

• 要求给出按字典序排列的第i个排列。
    我们设A[i]是用i个fences满足条件的组合数，显然我们无法找到合适的递归条件，于是我们把它分解：

   A[i]= sum(B[i, k]), k = 1,2,3...i #其中B[i, k]表示第k短打头的i个木棍的总的排列数。
  

此时，我们再尝试对B动规，找训B[i, k]和B[i - 1, j]之间的关系，但是第k短打头的时候，与i-1个木棍的所有排列可能又要分情况讨论，即：

     B[i, k] = sum(B[i - 1, j]) j = k, k + 1,..., i - 1 #后面的B都满足先降后升，即我们要把一个第k短的木板放到开头，使第二根比他高
     B[i, k] = sum(B[i - 1, j]) j = 1, 2, 3 ... , k - 1 #后面的B都满足先升后降，即我们要把一个第k短的木板放到开头，使第二根比他矮

于是，我们设C[i, k ,DOWN]表示第k短开头，并且满足先降后升的性质，C[i, k ,UP]表示第k短开头，并且满足先升后降的性质。这样，我们的递推关系就找到了：

 C[i, k, DOWN] = sum(C[i - 1, j, UP]) j = k, k + 1, ... , i-1
 C[i, k, UP]   = sum(C[i - 1, j, UP]) j = 1, 2, 3 ... , k-1

void solve(){
    int i,j,k;
    memset(dp, 0, sizeof(dp));
    dp[1][1][0] = dp[1][1][1] = 1;
    for(i = 2;i<=n;i++){
        for(j = 1;j<=i;j++){
            for(k = 1;k<=j-1;k++)
                dp[i][j][1] += dp[i-1][k][0];
            for(k = j;k<=i-1;k++)
                dp[i][j][0] += dp[i-1][k][1];
        }
    }
}

我们找到数目的递推关系之后，还要能找出任意某个排列的具体情况，即用到排序计数的思想：

举一个例子说明：假使我们有4根木棍，我们要求第三种排列
  * 1打头的总数B[4, 1] = 1,2打头的总数为B[4, 2] = 3，那我们就知道第二种排列就在2打头的里面，并且是第二个。第一个数字确定为2.
  * 2打头里面，先考虑DOWN的情况(因为DOWN的情况字典序一定小)C[4, 2, DOWN] = 1,C[4, 2, UP] = 2,于是总体的第三个就是C[4, 2, UP] 中第一个，即第二个数字确定为3.
  * 23打头里面DOWN的第一个为1，即第三个数字确定为1
  * 231打头里面第一个UP的数字为4，即第四个数字确定为4，所以结果就是2314。

代码很难写，还没写出来。。

作业题

• 方盒游戏