poj-1037

//196K  16MS    C++
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX = 25;

long long DP[MAX][MAX][2]; // 0: down. 1: up

void init() {
    for (int curPlankNum = 1; curPlankNum <= 20; curPlankNum++) {
        for (int beginPlankLength = 1; beginPlankLength <= curPlankNum; beginPlankLength++) {
            if (curPlankNum == 1) {
                DP[beginPlankLength][curPlankNum][0] = 1;
                DP[beginPlankLength][curPlankNum][1] = 1;
            } else {            
                for (int availLength = 1; availLength < curPlankNum; availLength++) {
                    if (availLength < beginPlankLength) {
                        DP[beginPlankLength][curPlankNum][0] +=
                            DP[availLength][curPlankNum-1][1];
                    } else if (availLength >= beginPlankLength) {
                        DP[beginPlankLength][curPlankNum][1] += 
                            DP[availLength][curPlankNum-1][0];
                    }
                }
            }   


            // printf("%d %d %d %lld\n", beginPlankLength, curPlankNum, 0, DP[beginPlankLength][curPlankNum][0]);
            // printf("%d %d %d %lld\n", beginPlankLength, curPlankNum, 1, DP[beginPlankLength][curPlankNum][1]);
        }
    }
}

void init2() {
 DP[1][1][0] = DP[1][1][1]=1;
    for(int len=2;len<=20;len++){
        for(int i=1;i<=len;i++){
            for(int j=1;j<i;j++) DP[i][len][0]+=DP[j][len-1][1];
            for(int j=i;j<=len;j++) DP[i][len][1]+=DP[j][len-1][0];
            printf("%d %d %d %lld\n", i, len, 0, DP[i][len][0]);
            printf("%d %d %d %lld\n", i, len, 1, DP[i][len][1]);
        }
    }
}

void init3() {
    DP[1][1][0] = 1; DP[1][1][1] = 1;
    DP[1][2][0] = 0; DP[1][2][1] = 1;
    DP[2][2][0] = 1; DP[2][2][1] = 0;
    for (int i = 3; i < 21; i++) {
        for (int j = 1; j < 21; j++) {
            for (int k = 1; k < j; k++) DP[j][i][0] += DP[k][i - 1][1];
            for (int k = j; k < i; k++) DP[j][i][1] += DP[k][i - 1][0];
            printf("%d %d %d %lld\n", i, j, 0, DP[j][i][0]);
            printf("%d %d %d %lld\n", i, j, 1, DP[j][i][1]);
        }
    }
}

int plankNum;
long long ordinalNum;
int caseNum;
int res[MAX];
int main() {
    init();
    // init2();
    scanf("%d", &caseNum);
    for (int i = 1; i <= caseNum; i++) {
        scanf("%d %lld", &plankNum, &ordinalNum);
        if (plankNum == 1) {
            printf("1\n");
            continue;
        }
        memset(res, 0, sizeof(res));
        int undecidedDigits = plankNum;
        char firstDigitDecided = 0;
        char prevDigit = 0;
        char prevDigitDirection = -1;
        char usedMap[25] = {0};
        while(undecidedDigits) {
            if (!firstDigitDecided) {
                long long acc = 0;
                int firstNumber = 1;
                for (; firstNumber <= plankNum; firstNumber++) {
                    acc += DP[firstNumber][plankNum][0];
                    if (acc >= ordinalNum) {
                        firstDigitDecided = 1;
                        acc -= DP[firstNumber][plankNum][0];
                        prevDigitDirection = 0;
                        break;
                    }
                    acc += DP[firstNumber][plankNum][1];
                    if (acc >= ordinalNum) {
                        firstDigitDecided = 1;
                        acc -= DP[firstNumber][plankNum][1];
                        prevDigitDirection = 1;
                        break;
                    }
                }
                // printf("firstNumber: %d\n", firstNumber);
                res[plankNum - undecidedDigits] = firstNumber;
                prevDigit = firstNumber;
                usedMap[firstNumber] = 1;
                ordinalNum -= acc;
            } else {
                long long acc = 0;
                int firstDigit = -1;
                if (prevDigitDirection == 1) {
                    // this time should up
                    int order = 1;
                    int possibleDigit = 1;
                    for (; possibleDigit <= plankNum; possibleDigit++) {
                        if (!usedMap[possibleDigit]) {
                            if (possibleDigit > prevDigit) {
                                acc += DP[order][undecidedDigits][0];
                                if (acc >= ordinalNum) {
                                    acc -= DP[order][undecidedDigits][0];
                                    prevDigitDirection = 0;
                                    break;
                                }
                            }
                            order++;
                        }
                    }
                    res[plankNum - undecidedDigits] = possibleDigit;
                    prevDigit = possibleDigit;
                    usedMap[possibleDigit] = 1;
                    ordinalNum -= acc;
                } else if (prevDigitDirection == 0) {
                    // this time should down
                    int order = 1;
                    int possibleDigit = 1;
                    for (; possibleDigit <= plankNum; possibleDigit++) {
                        if (!usedMap[possibleDigit]) {
                            if (possibleDigit < prevDigit) {
                                acc += DP[order][undecidedDigits][1];
                                if (acc >= ordinalNum) {
                                    acc -= DP[order][undecidedDigits][1];
                                    prevDigitDirection = 1;
                                    break;
                                }
                            }
                            order++;
                        }
                    }
                    res[plankNum - undecidedDigits] = possibleDigit;
                    prevDigit = possibleDigit;
                    usedMap[possibleDigit] = 1;
                    ordinalNum -= acc;
                }
            }
            undecidedDigits--;
        }
        for (int i = 0; i < plankNum; i++) {
            if (i < plankNum - 1) {
                printf("%d ", res[i]);
            } else if (i == plankNum - 1) {
                printf("%d\n", res[i]);
            }
        }
    }
}

经典的DP， 这道题让我对 DP中“相同类型的子问题” 理解更为深刻， 在开始分析这道题的时候，陷入了一个误区：

比如说，对于长度为4的fence，有1， 2 ，3， 4，5， 6，六块木板，

那么如果选2为头，剩下的木板就是 1， 3， 4，5，6  这时候，如果是上升方向的波浪型， 第2块木板就只能选择 3/4/5/6,

这时候如果选择 3, 那么还有 1, 4, 5,6 四块木板， 这时候似乎出现了一个与之前比较相同的子问题：

及都是在一定数量的木板的前提下，第一块木板是K， 求波浪方向向上/向下的fence方案总和：

但是需要注意的是，这里的"一定数量的木板" 是没有任何细节上的共性的（比如，虽然数量都是 5， 但可能是 1,2,  4, 5,6, 也可能是 1, 2, 3, 4 ,6），似乎不是相同类型的子问题，

这时候，就显示出抽象的强大了： 虽然 (1, 2, 4, 5 ,6) 和 (1,2,3,4, 6) 在细节上没有什么相似度，但都遵循一个规则：都是5块木板组合，并且都可以从小到大来进行排序。

这一点很重要，因为要关注的是在这种情况下的fence方案数量， 这个数量只和木板数量有关系，跟每块木板具体长度没有任何关系，只要木板的长度都是不等的，就可以进行排序组合：

举个例子：

3块木板 ：

1 8 9

和另外3块木板：

1 2 3

遵从题目的"波浪型"要求，能产生的fence方案数量都是一样的。

也就是，每个木板高度的细节在这里是不需要的（当然，在后面需要，判断波浪型的时候），只要有木板的数量就可以。

那么状态转移方程：

DP[i][j][0]: 表示当前有 j 块木板， 以 第 i 短的木板为第一块木板， 并且第二块木板高度比其低的前提下， 一共有多少种满足条件的fence方案。

DP[i][j][1]: 表示当前有 j 块木板， 以 第 i 短的木板为第一块木板， 并且第二块木板高度比其高的前提下， 一共有多少种满足条件的fence方案。

那么 DP[i][j][0] 就等于 SUM{DP[a1][j -1][1] ...DP[an][j -1][1].. DP[aN][j -1][1]}, 其中 an的 含义比较纠结：

an是在 j -1块木板中， 比