DAG建模基础；
传送门：$>here<$
n种长方体，各有无限个。可以横竖侧摆放。只有一个长方形的底面，长小于且宽小于令一个底面才可以叠在上面。问最多叠多高？
数据范围：$n \leq 30$
将木块的6种状态（不是3种）作为不同物体考虑。若a能在b下面，那么连一条a->b的边，权值为b的高。至于第一块的高，考虑使用虚拟点。
已经将所有可能情况归结在图中了。显然这个图一定无环。所以利用DAG的性质，$O(n^2)$求最长路即可。
DAG求最长路的本质是DP。设$dp[i]$表示从$i$出发的最长路，由于不会有环，所以用所有$i$连出去的点进行转移即可。换句话说这些连出去的点和$i$毫无关系，是个独立的子问题。之所以叫它DP，是因为DAG里是可以有重复的子问题的（树就没有）
二元关系可以利用图来建模。在这道题中，一块木块能否放在另一块上面是一个二元关系。而在建模过程中，每一个木块的状态是唯一的，像这种木块翻转的应当看做两种情况。
注意有6种，而不是3种。底面的长宽也是需要交换的！！！
当然在代码实现的过程中为了方便依然可以只存三种情况，因为底面长宽交换不影响高，所以可以以两种状态存在，至于放上来的木块，只要横竖以一种状态能够放上就可以。因为一块木块一旦放完，对于剩余的木块它就是底，因此横竖都无所谓。
/*By DennyQi 2019*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 10010; const int MAXM = 20010; const int INF = 0x3f3f3f3f; inline int Max(const int a, const int b){ return (a > b) ? a : b; } inline int Min(const int a, const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ ‘-‘ && (c < ‘0‘ || c > ‘9‘); c = getchar()); if(c == ‘-‘) w = -1, c = getchar(); for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) x = (x<<3) + (x<<1) + c - ‘0‘; return x * w; } struct Cuboid{ int x,y,z; }a[30001]; int n,N,Case,ans; int first[30001],nxt[30001],to[30001],cost[30001],cnt,dp[30001],pre[30001]; bool vis[30001]; inline bool Nest(int i, int j){ if((a[i].x>a[j].x && a[i].y>a[j].y) || (a[i].x>a[j].y && a[i].y>a[j].x)) return 1; return 0; } inline void add(int u, int v, int w){ cost[++cnt] = w, to[cnt] = v, nxt[cnt] = first[u], first[u] = cnt; } int Dfs(int u){ if(vis[u]) return dp[u]; vis[u] = 1; for(int i = first[u]; i; i = nxt[i]){ if(Dfs(to[i]) + cost[i] > dp[u]){ dp[u] = dp[to[i]] + cost[i]; pre[u] = to[i]; } } return dp[u]; } int main(){ while((N = read()) > 0){ n = N*3; memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); memset(first,0,sizeof(first)); for(int i = 1; i <= N; ++i){ a[i].x = read(), a[i].y = read(), a[i].z = read(); a[i+N].x = a[i].x, a[i+N].y = a[i].z, a[i+N].z = a[i].y; a[i+N*2].x = a[i].y, a[i+N*2].y = a[i].z, a[i+N*2].z = a[i].x; } for(int i = 1; i <= n; ++i){ add(n+1,i,a[i].z); } for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n; ++j){ if(i == j) continue; if(Nest(i,j)) add(i,j,a[j].z); } } ans = Dfs(n+1); ++Case; printf("Case %d: maximum height = %d\n",Case,ans); } return 0; }
[UVa-437] The Tower of Babylon
原文：https://www.cnblogs.com/qixingzhi/p/10366778.html