HDU1069

简单DP

题意:

给定一些block的xyz坐标。

求使得某些block叠起来得到的最大高度。

dp[ i ].ans=max( dp[ 0....i-1 ].ans );( 还必须满足block[ i ].x,block[ i ].y 都小于dp[ k ].x,dp[ k ].y );

View Code
 1 /*
 2 dp
 3 */
 4 #include<stdio.h>
 5 #include<string.h>
 6 #include<stdlib.h>
 7 #include<algorithm>
 8 #include<iostream>
 9 #include<queue>
10 //#include<map>
11 #include<math.h>
12 using namespace std;
13 typedef long long ll;
14 //typedef __int64 int64;
15 const int maxn = 205;
16 const int inf = 0x7fffffff;
17 const int pi=acos(-1.0);
18 struct node{
19     int x,y,z;
20 }block[ maxn ];
21 struct node2{
22     int x,y;
23     int ans;
24 }dp[ maxn ];
25 
26 bool cmp( node a,node b ){
27     if( a.x!=b.x ) return a.x>b.x;
28     else return a.y>b.y;
29 }
30 
31 int main(){
32     int n;
33     int T=1;
34     while( scanf("%d",&n)!=EOF , n ){
35         int cnt=0;
36         int a,b,c;
37         memset( dp,0,sizeof(dp) );
38         while( n-- ){
39             scanf("%d%d%d",&a,&b,&c);
40             block[ cnt ].x=a,block[ cnt ].y=b,block[ cnt ].z=c;
41             //dp[ cnt ].x=a,dp[ cnt ].y=b,dp[ cnt++ ].ans=c;
42             cnt++;
43             block[ cnt ].x=a,block[ cnt ].y=c,block[ cnt ].z=b;
44             //dp[ cnt ].x=a,dp[ cnt ].y=c,dp[ cnt++ ].ans=b;
45             cnt++;
46             block[ cnt ].x=b,block[ cnt ].y=a,block[ cnt ].z=c;
47             //dp[ cnt ].x=b,dp[ cnt ].y=a,dp[ cnt++ ].ans=c;
48             cnt++;
49             block[ cnt ].x=b,block[ cnt ].y=c,block[ cnt ].z=a;
50             //dp[ cnt ].x=b,dp[ cnt ].y=c,dp[ cnt++ ].ans=a;
51             cnt++;
52             block[ cnt ].x=c,block[ cnt ].y=b,block[ cnt ].z=a;
53             //dp[ cnt ].x=c,dp[ cnt ].y=b,dp[ cnt++ ].ans=a;
54             cnt++;
55             block[ cnt ].x=c,block[ cnt ].y=a,block[ cnt ].z=b;
56             //dp[ cnt ].x=c,dp[ cnt ].y=a,dp[ cnt++ ].ans=b;
57             cnt++;
58         }
59         sort( block,block+cnt,cmp );
60         //printf("cnt:%d\n",cnt);
61         dp[ 0 ].x=block[ 0 ].x,dp[ 0 ].y=block[ 0 ].y,dp[ 0 ].ans=block[ 0 ].z;
62         int ans=-1;
63         for( int i=1;i<cnt;i++ ){
64             int tmpx,tmpy,tmpans;
65             int flag=-1;
66             tmpx=block[ i ].x,tmpy=block[ i ].y;
67             tmpans=-1;
68             for( int j=0;j<i;j++ ){
69                 if( tmpx<dp[ j ].x && tmpy<dp[ j ].y ){
70                     if( tmpans<dp[ j ].ans ){
71                         flag=j;
72                         tmpans=dp[ j ].ans;
73                     }
74                 }
75             }
76             //printf("flag:%d \n",flag);
77             if( flag==-1 )
78                 dp[ i ].x=block[ i ].x,dp[ i ].y=block[ i ].y,dp[ i ].ans+=block[ i ].z;
79             else 
80                 dp[ i ].x=block[ i ].x,dp[ i ].y=block[ i ].y,dp[ i ].ans=dp[ flag ].ans+block[ i ].z;
81             //printf("dp[ %d ]: x:%d y:%d ans:%d \n\n",i,dp[i].x,dp[i].y,dp[i].ans);
82             ans=max( ans,dp[i].ans );
83         }
84         printf("Case %d: maximum height = %d\n",T++,ans);
85         //printf("%d\n",dp[ cnt-1 ].ans);
86     }
87     return 0;
88 }
keep moving...
原文地址:https://www.cnblogs.com/xxx0624/p/2826844.html