Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem A: Russian Dolls

Russian nesting dolls are brightly painted hollow wooden figures. The dolls in a set have roughly the same shape, typically humanoid, but different sizes. When the set is assembled, the biggest doll contains the second-biggest doll, the second-biggest contains the third-biggest, and so on.

We can approximate the shape of a doll as a cylinder of height h, diameter d, and wall thickness w. Such a doll would have a hollow of height h-2w and diameter d-2w.

Boris and Natasha each has a set of dolls. The sets are nearly identical; each has the same number of dolls, which look the same but differ in their dimensions. Last night Boris and Natasha were playing with their dolls and left them in the living room. Their mother tidied them away, dumping them all in one box. Can you help Boris and Natasha separate their sets of dolls?

Standard Input will consist of several test cases. The first line of each test case will contain n, the number of dolls in each set (1 < n <= 100). 2n lines follow; each gives the dimensions, h, d, w of a different doll (h,d >= 2w > 0). A line containing 0 follows the last test case.

For each test case, separate the dolls into two sets of nesting dolls such that, within each set, the dolls fit within each other, standing straight up, as described above. The first n lines of output should give the dimensions of the dolls in one set, in decreasing order by height. The next line should contain a single hyphen, "-". The next n lines should give the dimensions of the dolls in the second set, also in decreasing order by height. There will always be a solution. If there are many solutions, any will do. Output an empty line between test cases.

Sample Input

3
100 100 3
97 97 3
94 94 3
91 91 3
88 88 3
85 85 3
5
100 100 1
97 97 3
98 98 1
96 96 1
94 94 1
92 92 1
90 90 1
88 88 1
86 86 1
84 84 1
0

Possible Output

100 100 3
94 94 3
88 88 3
-
97 97 3
91 91 3
85 85 3

100 100 1
98 98 1
96 96 1
94 94 1
92 92 1
-
97 97 3
90 90 1
88 88 1
86 86 1
84 84 1

---

G. V. Cormack

題目描述：

有兩組俄羅斯套娃，每組都有 n 個，現在要將凌亂的 2n 個套娃分兩組回去，
並且輸出任一分組方式，每一組確切要 n 個。

題目解法：

首先，要對寬或直徑排序，用來待會的窮舉搜索時使用。

窮舉搜索時，當窮舉到第 i 個應該分給第一組還是第二組時，就確保前 i 組都已經分配好了。

因此可以利用分配的狀態 (第一組的最後一個，第二組的最後一個，第一組個數)

// 根據這個搜索狀態進行重複情況的剪枝，個人覺得不太像是動態規劃。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Doll {
    int h, d, w;
    Doll(int a=0, int b=0, int c=0):
        h(a), d(b), w(c) {}
    bool operator<(const Doll &a) const {
        return h < a.h;
    }
};
char used[205][205][105];
int n, findflag;
Doll D[205];
vector<int> ret1, ret2;
int containDoll(int a, int b) {
    if(a == 0)    return 1;
    int hh = D[b].h - 2 * D[b].w;
    int dd = D[b].d - 2 * D[b].w;
    return hh >= D[a].h && dd >= D[a].d;
}
void dfs(int f1, int f2, int f1count) {
    int idx = max(f1, f2) + 1;
    if(findflag)    return;
    if(max(f1, f2) - f1count > n)
        return;
    if(idx == n * 2 + 1 && f1count == n) {
        findflag = 1;
        for(int i = n-1; i >= 0; i--) {
            idx = ret1[i];
            printf("%d %d %d\n", D[idx].h, D[idx].d, D[idx].w);
        }
        puts("-");
        for(int i = n-1; i >= 0; i--) {
            idx = ret2[i];
            printf("%d %d %d\n", D[idx].h, D[idx].d, D[idx].w);
        }
        return;
    }
    if(used[f1][f2][f1count]) // cut;
        return;
    used[f1][f2][f1count] = 1;
    if(containDoll(f1, idx) && f1count+1 <= n) {
        ret1.push_back(idx);
        dfs(idx, f2, f1count+1);
        ret1.pop_back();
    }
    if(containDoll(f2, idx)) {
        ret2.push_back(idx);
        dfs(f1, idx, f1count);
        ret2.pop_back();
    }
}
int main() {
    int i, j, k;
    int cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        int n2 = n * 2;
        for(i = 1; i <= n2; i++)
            scanf("%d %d %d", &D[i].h, &D[i].d, &D[i].w);
        sort(D+1, D+1+n2);
        memset(used, 0, sizeof(used));
        ret1.clear(), ret2.clear();
        findflag = 0;
        if(cases++)
            puts("");
        dfs(0, 0, 0);
    }
    return 0;
}