hdu 1069 Monkey and Banana（记忆搜）

题意：

N（不超过30）种木块，每种木块有长、宽、高x,y,z。

木块A可以搭在木块B上当且仅当A的底面长和宽都分别小于B的顶面的长与宽，即不能有超出B的部分。

问垒起来的“木块塔”的最大高度。

思路：

每种木块有6种形态，所以总共有6*N种木块，列张二维关系表，然后记忆搜。

代码：

struct node{

    int x,y,z;

}

b[355];

int dp[355];

int c;

bool mp[355][355];

int dfs(int x){

    if(dp[x]!=-1) return dp[x];

    bool yes = false;

    rep(i,1,c) if(mp[x][i]){

        dp[x] = max( dp[x],dfs(i)+b[x].z );

        yes = true;

    }

    if(yes==false){

        dp[x]=b[x].z;

    }

    return dp[x];

}

int main(){

    int n;

    int T=0;

    while(scanf("%d",&n)!=EOF && n>0){

        rep(i,1,n){

            scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);

        }

        c = n;

        rep(i,1,n){

            b[++c].x=b[i].y;  b[c].y=b[i].x;    b[c].z=b[i].z;

            b[++c].x=b[i].x;  b[c].y=b[i].z;    b[c].z=b[i].y;

            b[++c].x=b[i].z;  b[c].y=b[i].y;    b[c].z=b[i].x;

            b[++c].x=b[i].z;  b[c].y=b[i].x;    b[c].z=b[i].y;

            b[++c].x=b[i].y;  b[c].y=b[i].z;    b[c].z=b[i].x;

        }

        mem(mp,false);  //mp[i][j]==true：第i种可以放到第j种上

        rep(i,1,c){

            rep(j,1,c){

                if(b[i].x<b[j].x && b[i].y<b[j].y){

                    mp[i][j]=true;

                }

                if(b[i].x>b[j].x && b[i].y>b[j].y){

                    mp[j][i]=true;

                }

            }

        }

        mem(dp,-1);

        int ans = -1;

        rep(i,1,c){

            if(dp[i]==-1){

                ans = max( ans,dfs(i) );

            }else{

                ans = max( ans,dp[i] );

            }

        }

        printf("Case %d: maximum height = %d\n",++T,ans);

    }

    return 0;

}

巴特西

hdu 1069 Monkey and Banana（记忆搜）

最新文章

热门文章