hdu1069 Monkey and Banana

题目大意 给你n种砖块，问最高能垒多高，要求上层砖块严格小于下层，高度无限制

一开始想的简单了一点，因为n非常小（30以内），就在输入的时候遍历一下判断当前砖块能不能放在之前的砖块上面或者下面，有的话建一条边，最后从每个位置试一下所有边的情况遍历一下就出来了

然后试样例时候一拍脑袋想起来。。砖块可以转。。实际相当于一块顶六块。。然后重新改了改思路还是一致的，就是每次输入相当于输入六个。。

提交之后emmmm TLE（ 好吧 可能是多组输入这个太暴力了导致的。。

毕竟是DP的题目嘛。。就想想怎么用DP解决。。后来仔细思考一下 DP其实可以说是记忆化搜索，我这个暴力的算法浪费时间就是从每种砖头找边时候实际上找了好几次同样的结果。。那我暂存一下每种砖头的结果不就可了 然后就可以了。。

++

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> G[200];
struct block{
    int x,y,z;
    int maxhei;
}blocks[200];
bool checkblock(int i,int j){
    return (blocks[i].x<blocks[j].x)&&(blocks[i].y<blocks[j].y);
}
int findlongest(int t){
    if(blocks[t].maxhei){
        return blocks[t].maxhei;
    }
    int res=blocks[t].z;
    int tmp=0;
    for(int i=0;i<G[t].size();++i){
        tmp=max(tmp,findlongest(G[t][i]));
    }
    blocks[t].maxhei=res+tmp;
    return res+tmp;
}
int main(){
    int n;
    int T=1;
    while(scanf("%d",&n),n){
        for(int i=0;i<n;++i){
            int x[3];
            scanf("%d%d%d",&x[0],&x[1],&x[2]);
            for(int t=0;t<6;++t){
                G[i*6+t].clear();
                blocks[i*6+t].maxhei=0;
            }
            blocks[i*6].x=x[0],blocks[i*6].y=x[1],blocks[i*6].z=x[2];
            blocks[i*6+1].x=x[0],blocks[i*6+1].y=x[2],blocks[i*6+1].z=x[1];
            blocks[i*6+2].x=x[1],blocks[i*6+2].y=x[2],blocks[i*6+2].z=x[0];
            blocks[i*6+3].x=x[1],blocks[i*6+3].y=x[0],blocks[i*6+3].z=x[2];
            blocks[i*6+4].x=x[2],blocks[i*6+4].y=x[0],blocks[i*6+4].z=x[1];
            blocks[i*6+5].x=x[2],blocks[i*6+5].y=x[1],blocks[i*6+5].z=x[0];
            for(int t=0;t<6;++t){
                for(int j=i*6+t-1;j>=0;--j){
                    if(checkblock(i*6+t,j)){
                        G[j].push_back(i*6+t);
                    }
                    if(checkblock(j,i*6+t)){
                        G[i*6+t].push_back(j);
                    }
                }
            }
        }
        int res=0;
        for(int i=0;i<n*6;++i){
            res=max(res,findlongest(i));
        }
        printf("Case %d: maximum height = %d\n",T,res);
        ++T;
    }
    return 0;
}