Monkey and Banana

HDOJ-1069

这里实际是嵌套矩形问题的变式，也就是求不固定起点的最长路径
动态转移方程为：dp[i]=max(dp[j]+block[i].h|(i,j)∈map)，这里的dp[i]表示从i块出发的可以构建的最大的高度。
首先需要构建出图map，表示一块是否可以搭建在另一块上面。
还有一个问题就是需要进行排序，我是按照面积进行从小到大排序的。如果不排序，可能AC不了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

using namespace std;

int n;

int cnt;//实际所有的块数

struct node{

    int x;

    int y;

    int h;

    node(){};

    node(int x1,int y1,int h1):x(x1),y(y1),h(h1){}

    bool operator<(const node& t)const{

        return x*y<t.x*t.y;

    }

};

node block[90];

//vector<node> map[99];

int map[99][99];

int dp[99];//dp[i]表示从i出发可以达到的最高高度

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k=0;

    while(cin>>n&&n){

        cnt=0;

        int x,y,z;

        for(int i=0;i<n;i++){

            cin>>x>>y>>z;

            block[cnt++]=node(x,y,z);

            block[cnt++]=node(x,z,y);

            block[cnt++]=node(y,z,x);

        }

        sort(block,block+cnt);//一定要排序

        for(int i=0;i<cnt;i++){

            for(int j=0;j<cnt;j++){

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

                    map[i][j]=1;

                }else{

                    map[i][j]=0;

                }

            }

        }

        for(int i=0;i<cnt;i++)

            dp[i]=block[i].h;

        int maxs=0;

        for(int i=0;i<cnt;i++){

            dp[i]=block[i].h;//这里一定要初始化为它相应的高度，因为从这一块开始出发，其实高度必须是它自己本身的高度

            for(int j=0;j<i;j++){

                if(map[i][j]){//j可以放在i上面

                    dp[i]=max(dp[i],dp[j]+block[i].h);

                }

            }

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

        //cout<<dp[i]<<endl;

        }

        cout<<"Case "<<++k<<": maximum height = "<<maxs<<endl;

        //cout<<maxs<<endl;

    }

    return 0;

}

巴特西

HDOJ-1069(动态规划+排序+嵌套矩形问题)

Monkey and Banana

HDOJ-1069

最新文章

热门文章