一、题意

有n（n<=30）种立方体，每种有无穷个。现在要求你选一些立方体摞成尽量高的一个柱子，上面的立方体底面长宽必须严格小于下面的立方体。问最大高度。

二、解析

由于上面的立方体底面长宽必须严格小于下面的立方体，因此不会出现环，也就是说这是一个典型的DAG（有向无环图）问题。

有向无环图可以通过记忆化搜索（动态规划）的方式来解决，因此直接套用模板即可。
唯一要注意的是这道题里的状态需要用两个参数来表示，即i, k。i表示这是第几种立方体，k表示这个立方体哪条边作为高。因此记忆化搜索是状态的存放数据memo也应该是两维的。

三、代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 30 + 5;
int kase = 1, n, a[maxn][3], memo[maxn][3];

bool isFit(int v, int vk, int u, int uk) {
    int va = a[v][(vk + 1) % 3], vb = a[v][(vk + 2) % 3];
    int ua = a[u][(uk + 1) % 3], ub = a[u][(uk + 2) % 3];
    return va < ua && vb < ub || va < ub && vb < ua;
}

int dp(int u, int uk) {
    int & res = memo[u][uk];  // 记忆化搜索
    if(res != -1) return res;

    res = a[u][uk];
    for(int v = 0; v < n; v ++) for(int vk = 0; vk < 3; vk ++) {
        if(isFit(v, vk, u, uk)) res = max(res, a[u][uk] + dp(v, vk));
    }
    return res;
}

int main() {
    while(cin >> n && n) {
        for(int i = 0; i < n; i ++) cin >> a[i][0] >> a[i][1] >> a[i][2];
        memset(memo, -1, sizeof(memo));
        int ans = 0;
        for(int i = 0; i < n; i ++) for(int k = 0; k < 3; k ++) ans = max(ans, dp(i, k));
        cout << "Case " << kase ++ << ": maximum height = " << ans << endl;
    }
}

四、归纳

  • 当问题中出现单向依赖关系时，可以考虑转化为DAG问题进行处理
  • DAG问题的最长路问题可以通过记忆化搜索来解决，在DAG最长路问题中，dp(i)表示以i为起点的最长路。
    模板大致为： 
int dp(int u) {
    int & res = memo[u];  // 记忆化搜索
    if(res != -1) return res;

    res = ...;
    for(int v = 0; v < n; v ++) if([依赖条件]) {
        res = max(res, dp(v, vk) + ....);
    }
    return res;
}
  • 通过引用的方式引用memo，就不容易忘记记录结果到memo中
  • 记忆化搜索的时间复杂度 = 状态数 * 每个状态的决策数量。在本题中就是 3n * 3n = O(n^2)