题意：给n种砖块，每种可以随便用几次，每块有长宽高，要求把它们磊起来，求放在上面的砖块的长宽严格小于下面的砖块。
思路：考虑用dp 紫书上往前翻几页有详细的解法，DAG上的最长路问题，我用了n^2的记忆化搜索，以前用先排序再dp好像可以达到O(n)的效率。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define maxn 1100 using namespace std; int blocks[maxn][3]; int dp[maxn][3]; int cas = 1,n; int dfs(int i,int j,int now_h,int now_w) { int &ans = dp[i][j]; if(ans > 0) return ans; ans = 0; for(int t = 0;t< n;t++){ for(int k=0;k<3;k++){ int h,w; if(k == 0) h = blocks[t][1],w =blocks[t][2]; else if(k == 1) h = blocks[t][0],w =blocks[t][2]; else h = blocks[t][0],w =blocks[t][1]; if(h < now_h && w <now_w) ans = max(ans,dfs(t,k,h,w)); } } ans+=blocks[i][j]; return ans; } int main() { while(~scanf("%d",&n) && n){ memset(dp,0,sizeof dp); for(int i =0;i<n;i++){ scanf("%d%d%d",&blocks[i][0],&blocks[i][1],&blocks[i][2]); sort(blocks[i],blocks[i]+3); } int ans = 0; for(int i = 0;i<n;i++){ for(int j=0;j<3;j++){ int h,w; if(j == 0) h = blocks[i][1],w =blocks[i][2]; else if(j == 1) h = blocks[i][0],w =blocks[i][2]; else h = blocks[i][0],w =blocks[i][1]; ans=max(ans,dfs(i,j,h,w)); } } printf("Case %d: maximum height = %d\n",cas++,ans); } return 0; }
