HDU 4001 To Miss Our Children Time(DAG上的动态规划)

待我称王封你为后i 2024-02-17 19:17 36阅读 0赞

题意：  
输入n行，每行给出砖的长，宽，高，属性（a，b，c，d）；  
d＝0：该砖的长度和宽度要大于等于下面的砖的长，宽；即 长>=长，宽>=宽  
d＝1：该砖的长度和宽度要大于等于下面的砖的长，宽；同时，该砖的面积要比下面的砖的面积大；即长>=长，宽>=宽，面积>面积。也就是长>=长&&宽>=宽&&（长>长||宽>宽）

d＝2：该砖的长度和宽度要大于下面的砖的长，宽；长>长，宽>宽。

先按长、宽 从小到大排序，再按d值从大到小排序；

注意：长宽可以交换！！

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+10;
    int n;
    long long dp[maxn];
    struct node{
    	int a,b,c,d;
    	node(int a=0,int b=0,int c=0,int d=0):a(a),b(b),c(c),d(d){}
    	bool operator<(const node& n)const {
    	if(a!=n.a)return a<n.a;
    	if(b!=n.b)return b<n.b;
    	return d>n.d;
    	}
    }nt[maxn];
    
    int main(){
    	while(scanf("%d",&n)==1 && n){
    		for(int i=0;i<n;i++){
    			int a,b,c,d;
    			scanf("%d%d%d%d",&a,&b,&c,&d);
    			if(a<b){int temp=a;a=b;b=temp;}
    			nt[i]=node(a,b,c,d);
    		}
    		sort(nt,nt+n);
    		memset(dp,0,sizeof(dp));
    		long long  ans=-1e5;
    		for(int i=0;i<n;i++)
    		  {
    		  	dp[i]=nt[i].c;
    		  	for(int j=0;j<i;j++){
    		  		switch(nt[i].d){
    		  			case 0:{
    		  				if(nt[i].a>=nt[j].a && nt[i].b>=nt[j].b)
    		  				dp[i]=max(dp[i],dp[j]+nt[i].c);
    						break;
    					  }
    					  case 1:{
    					  	if(nt[i].a>=nt[j].a && nt[i].b>=nt[j].b && (nt[i].a>nt[j].a||nt[i].a>nt[j].b))
    					  	dp[i]=max(dp[i],dp[j]+nt[i].c);
    						break;
    					  }
    					  case 2:if(nt[i].a>nt[j].a && nt[i].b>nt[j].b)
    					  	dp[i]=max(dp[i],dp[j]+nt[i].c);
    				  }
    			  }
    			  ans=max(ans,dp[i]);
    		  }
    		printf("%lld\n",ans);
    	}
    	return 0;
    }