紫书动规例题9-2 UVA

题目链接:

题意:

题解:

dp[i][j]:=考虑到前i个立方体并且第i个立方体以标号为j为高的最大值

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n;
19 int block[40][3],d[40][3];
20 
21 void get(int* v,int b,int x){
22     int idx = 0;
23     for(int i=0; i<3; i++)
24         if(i!=x)
25             v[idx++] = block[b][i];
26 }
27 
28 int dp(int i,int j){
29     if(d[i][j] >= 0) return d[i][j];
30     d[i][j] = 0;
31     int v[2],v2[2];
32     get(v,i,j);
33     for(int a=0; a<n; a++){
34         for(int b=0; b<3; b++){
35             get(v2,a,b);
36             if(v[0]>v2[0] && v[1]>v2[1])
37                 d[i][j] = max(d[i][j],dp(a,b));
38         }
39     }
40     d[i][j] += block[i][j];
41     return d[i][j];
42 }
43 
44 int main(){
45     int cas = 0;
46     while(scanf("%d",&n) && n){
47         for(int i=0; i<n; i++){
48             scanf("%d%d%d",&block[i][0],&block[i][1],&block[i][2]);
49             sort(block[i],block[i]+3);
50         }
51 
52         int ans = -INF;
53         memset(d,-1,sizeof(d));
54         for(int i=0; i<n; i++)
55             for(int j=0; j<3; j++)
56                 ans = max(ans,dp(i,j));
57         printf("Case %d: maximum height = %d
",++cas,ans);
58     }
59 
60     return 0;
61 }

紫书动规 例题9-2 UVA

题目链接:

题意:

题解:

代码:

紫书动规例题9-2 UVA