hdoj1069 Monkey and Banana（DP--LIS）-蒲公英云

hdoj1069 Monkey and Banana（DP--LIS）

朱雀 2021-12-21 01:07 305阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069

思路：

由题意，显然一种block可能有6种形式，且一种形式最多使用一次，因此最多有30×6=180个block。然后先按长进行排序，若长相同，则按宽进行排序。这样排序之后整个问题就变成了求这个排列的上升子序列的最高值，就转变成求LIS。由于数据量小，用经典的O(n^2)LIS算法即可（关于LIS算法可以见我的另一片随笔：https://www.cnblogs.com/FrankChen831X/p/10384238.html），由于最长的上升子序列的高度不一定是最大的，所以LIS的O(nlogn0算法不能用。详见代码，代码中f\[i\]表示以i结尾的最高的上升子序列的高度值。做这道题被一个小错误硬生生卡了5个小时，卡到怀疑人生，就是我在初始化b\[k\]的同时初始化f\[k\]，这样排序之后与原来的不匹配了，欸，这么小的错误找了半天，只能吸取教训了。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct block{
 5     int x,y,z;
 6 }b[185];
 7 
 8 bool cmp(block aa,block bb){
 9     if(aa.x<bb.x) return 1;
10     else if(aa.x==bb.x&&aa.y<bb.y) return 1;
11     else return 0;
12 }
13 
14 int n,x,y,z,cas=1,f[185];
15 
16 int main(){
17     while(scanf("%d",&n)!=EOF&&n){
18         int k=0,res=0;
19         while(n--){
20             scanf("%d%d%d",&x,&y,&z);
21             b[k].x=x;b[k].y=y;b[k].z=z;k++;
22             b[k].x=x;b[k].y=z;b[k].z=y;k++;
23             b[k].x=y;b[k].y=x;b[k].z=z;k++;
24             b[k].x=y;b[k].y=z;b[k].z=x;k++;
25             b[k].x=z;b[k].y=x;b[k].z=y;k++;
26             b[k].x=z;b[k].y=y;b[k].z=x;k++;    
27         }
28         sort(b,b+k,cmp);
29         for(int i=0;i<k;i++){
30             f[i]=b[i].z;
31             for(int j=0;j<i;j++)
32                 if(b[j].x<b[i].x&&b[j].y<b[i].y)
33                     f[i]=max(f[i],f[j]+b[i].z);
34             if(f[i]>res) res=f[i];
35         }
36         printf("Case %d: maximum height = %d\n",cas++,res);
37     }
38     return 0;
39 }