HDU 4001 To Miss Our Children Time(DP LIS)

제목 대의: 나무토막의 길이와 넓이를 정하고 번호를 매긴다. 1. 번호가 0이면 현재 나무토막의 길이(&&넓이)>= 아래 나무토막의 길이(넓이)2, 번호가 1이면 현재 나무토막의 길이(&&넓이)>= 아래 나무토막의 길이(넓이) & 면적도 아래 나무토막의 면적보다 3이 크고 번호가 0이면 현재 나무토막의 길이(&넓이)>아래 나무토막의 길이(넓이)를 만족시켜야 한다.
사고방식: DP와 유사한 LIS는 높이만 구할 수 있다. 데이터를 입력한 후에 정렬에 주의하고 구조체의 모든 구성원이 정렬해야 한다. 데이터가 조건에 부합되지 않을 때 dp[]가 정확하게 초기화하면 적지 않은 역할을 한다. 그 다음에 폭력적인 DP가 가장 큰 역할을 한다.

#include<map>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
#define LL __int64
#define inf 0x3f3f3f3f
const double PI=acos(-1.0);
using namespace std;
LL dp[1010];
struct node{
    LL l,w,h,d;
}q[1010];

LL op(node a,node b){
    if(a.l!=b.l)
        return a.l<b.l;
    if(a.w!=b.w)
        return a.w<b.w;
    if(a.h!=b.h)
        return a.h<b.h;
    if(a.d!=b.d)
    return a.d>b.d;
}

int main(){
    LL n,m,i,j,k,l,w,h;

    while(~scanf("%I64d",&n)&&n){
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;++i){
            scanf("%I64d%I64d%I64d%I64d",&q[i].l,&q[i].w,&q[i].h,&q[i].d);
            if(q[i].w>q[i].l){
                swap(q[i].w,q[i].l);
            }
        }
        sort(q,q+n,op);
        LL ans=0;
        for(i=0;i<n;++i){
            dp[i]=q[i].h;
            for(j=0;j<i;++j){
                LL now=q[i].l*q[i].w;
                LL pre=q[j].l*q[j].w;
                LL nl=q[i].l,nw=q[i].w;
                LL pl=q[j].l,pw=q[j].w;
                if( (nl>pl&&nw>pw)&&q[i].d==2&&(dp[i]<(dp[j]+q[i].h) ) ){
                    dp[i]=dp[j]+q[i].h;
                }
                if((nl>=pl)&&(nw>=pw)&&q[i].d==0&&( dp[i]<(dp[j]+q[i].h) ) ){
                    dp[i]=dp[j]+q[i].h;
                }
                if( (nl>=pl)&&(nw>=pw)&&(now>pre)&&q[i].d==1&&(dp[i]<(dp[j]+q[i].h) ) )
                    dp[i]=dp[j]+q[i].h;
            }
            if(ans<dp[i])
                ans=dp[i];
        }
        printf("%I64d
",ans);
    }
    return 0;
}