首页 > 代码库 > HDU 4001 To Miss Our Children Time （动态规划）

HDU 4001 To Miss Our Children Time （动态规划）

2024-07-15 14:31:25   221人阅读

To Miss Our Children Time


Problem Description
Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game will brings us lots of happy time! LLL is a nostalgic boy, now he grows up. In the dead of night, he often misses something, including a simple game which brings him much happy when he was child. Here are the game rules: There lies many blocks on the ground, little LLL wants build "Skyscraper" using these blocks. There are three kinds of blocks signed by an integer d. We describe each block‘s shape is Cuboid using four integers ai, bi, ci, di. ai, bi are two edges of the block one of them is length the other is width. ci is 
thickness of the block. We know that the ci must be vertical with earth ground. di describe the kind of the block. When di = 0 the block‘s length and width must be more or equal to the block‘s length and width which lies under the block. When di = 1 the block‘s length and width must be more or equal to the block‘s length which lies under the block and width and the block‘s area must be more than the block‘s area which lies under the block. When di = 2 the block length and width must be more than the block‘s length and width which lies under the block. Here are some blocks. Can you know what‘s the highest "Skyscraper" can be build using these blocks?
 

Input
The input has many test cases. 
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks. 
From the second to the n+1‘th lines , each line describing the i‐1‘th block‘s a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2). 
The input end with n = 0.
 

Output
Output a line contains a integer describing the highest "Skyscraper"‘s height using the n blocks.
 

Sample Input
3
10 10 12 0
10 10 12 1
10 10 11 2
2
10 10 11 1
10 10 11 1
0
 

Sample Output
24
11
 

Source
The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  4007 4003 4008 4005 4009 
 

题目大意：

有n块砖头，每块砖头有长，宽，高和型号，问你最多建多高？

型号0的特点是：长度>=它下面砖头的长度 且 宽度>=它下面砖头的宽度

型号1的特点是：长度>=它下面砖头的长度 且 宽度>=它下面砖头的宽度 且 面积>=它下面砖头的面积

型号2的特点是：长度>它下面砖头的长度 且 宽度>它下面砖头的宽度


解题思路：

先排好序，排序方法贪心的方法，先按长后按宽从小到大排，如果长宽相等就按照型号从大到小排，如果再相等，按照高度从大到小排，高度其实无所谓，但是这样更科学吧。

然后DP的思维，目前有两栋楼如果相同最顶上的砖头相同的话，取高度最大的楼。


解题代码：

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1100;

struct nodex{
    int l,w,h,id;
    friend bool operator < (nodex x,nodex y){
        if(x.l!=y.l) return x.l<y.l;
        else if(x.w!=y.w) return x.w<y.w;
        else if(x.id!=y.id) return x.id>y.id;
        else return x.h>y.h;

    }
}a[maxn];

struct node{
    int num;
    long long h;
    node(int num0=0,long long h0=0){
        num=num0;h=h0;
    }
};

long long dp[maxn],n;

void input(){
    a[0].l=a[0].w=a[0].h=a[0].id=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&a[i].l,&a[i].w,&a[i].h,&a[i].id);
        if(a[i].w>a[i].l) swap(a[i].w,a[i].l);
    }
    for(int i=0;i<=n;i++){
        dp[i]=-1;
    }
    sort(a,a+n+1);
}

void solve(){
    queue <node> q;
    q.push(node(0,0));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        while(!q.empty()){
            node s=q.front();
            q.pop();
            nodex tmp=a[s.num];
            if(a[i].id==0){
                if(a[i].l>=tmp.l && a[i].w>=tmp.w){
                    if(s.h+a[i].h>dp[i] ) dp[i]=s.h+a[i].h;
                }
            }else if(a[i].id==1){
                if( (a[i].l>=tmp.l && a[i].w>tmp.w) || (a[i].l>tmp.l && a[i].w>=tmp.w) ){
                    if(s.h+a[i].h>dp[i] ) dp[i]=s.h+a[i].h;
                }
            }else{
                if(a[i].l>tmp.l && a[i].w>tmp.w){
                    if(s.h+a[i].h>dp[i] ) dp[i]=s.h+a[i].h;
                }
            }
        }
        for(int t=0;t<=n;t++){
            if(dp[t]!=-1) q.push(node(t,dp[t]));
        }
    }
    long long ans=0;
    for(int i=0;i<=n;i++){
        if(dp[i]>ans) ans=dp[i];
    }
    cout<<ans<<endl;
}

int main(){
    while(scanf("%d",&n)!=EOF && n!=0){
        input();
        solve();
    }
    return 0;
}






联系
我们