uva 437 动态规划

题目链接戳这里

The Tower of Babylon 参考紫书

有n(n<=30)种立方体，每种都有无穷多个。 要求选一些立方体摞成一根尽量高的柱子
(可以自行选择哪一条边作为高)，使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。

由于增加的立方体后长宽严格减小,所以是一个DAG,相当于求DAG最长路.任何时候,只有顶面的尺寸会影响后续决策.所以用二元组(a,b)来表示顶面尺寸为a*b的状态.

但是由于a,b可能很大,所以用(idx,k)来间接表达.表示编号为idx的立方体在最上面,且高为k,那么面积自然就是立方体另外2个参数之积了

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
const int inf = 0x3f3f3f3f, maxN = 35;
int N, lft[maxN][3], d[maxN][3];
// 状态[idx,k] 即当前顶面为立方体idx,其中第k条边[排序后]为高

// 求得顶面面积的长宽
void get_mj(int *v, int i, int j) {
    int cnt = 0;
    rep(a, 0, 3)
        if (a != j)
            v[cnt++] = lft[i][a];
}

int dp(int i, int j) {
    int &ans = d[i][j];
    if (ans > 0)
        return ans;

    int v[2], vt[2];
    get_mj(v, i, j);
    ans = 0;
    rep(ii, 0, N) {
        rep(jj, 0, 3) {
            get_mj(vt, ii, jj);
            if (vt[0] < v[0] && vt[1] < v[1]) {
                ans = max(ans, dp(ii, jj));
            }
        }
    }
    ans += lft[i][j];
    return ans;
}

int main() {
    // freopen("data.in", "r", stdin);
    int kase = 0;
    while (~scanf("%d", &N) && N) {
        rep(i, 0, N) {
            rep(j, 0, 3)
                scanf("%d", &lft[i][j]);
            sort(lft[i], lft[i] + 3);
        }
        mst(d, 0);
        int ans = 0;
        rep(i, 0, N)
            rep(j, 0, 3)
                ans = max(ans, dp(i, j));
        printf("Case %d: maximum height = %d\n", ++kase, ans);
    }

    return 0;
}