思路：
我们可以先将一种箱子拆成3个不可移动的箱子。
接着，若b箱子能放在a上，就从a引一条箭头指向b。
以此类推，最终形成一张有向无环图。
最后，用记忆化搜索得到答案。
代码如下：
#include <bits/stdc++.h> #pragma GCC optimize(2) using namespace std; template < typename T > void read(T &x) { int f = 1;x = 0;char c = getchar(); for (;!isdigit(c);c = getchar()) if (c == ‘-‘) f = -f; for (; isdigit(c);c = getchar()) x = x * 10 + c - ‘0‘; x *= f; } bool G[305][305]; struct node { int a, b, c; }a[305]; int vis[305]; int n; int dfs(int dep) { if(vis[dep]) return vis[dep]; bool flag = 1; int maxn = INT_MIN; for(int i = 1;i <= n;i++) if(G[dep][i] == 1) { flag = 0; maxn = max(maxn, dfs(i)); } if(flag == 1) { vis[dep] = a[dep].c; return a[dep].c; } vis[dep] = a[dep].c + maxn; return vis[dep]; } int main() { //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); cin >> n; for(int i = 1;i <= n;i++) { read(a[i].a); read(a[i].b); read(a[i].c); } for(int i = 1;i <= n;i++) { a[n + i].c = a[i].a; a[n + i].b = a[i].c; a[n + i].a = a[i].b; a[2 * n + i].c = a[i].b; a[2 * n + i].b = a[i].c; a[2 * n + i].a = a[i].a; } n *= 3; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) if(min(a[i].a, a[i].b) > min(a[j].a, a[j].b) && max(a[i].a, a[i].b) > max(a[j].a, a[j].b)) G[i][j] = 1; int ans = INT_MIN; for(int i = 1;i <= n;i++) ans = max(ans, dfs(i)); cout << ans << endl; return 0; }
原文：https://www.cnblogs.com/fy4815/p/12548228.html
