C - Monkey and Banana
參考:ACM HDU 1069 Monkey and Banana (動态規劃)
思路:對于這道DP題來說,如果以高度或者說磚塊的個數來作為儲存的狀态的内容,顯然是不合适的。
不難看出,這道題主要是想求一個最長有序子序列,那麼我們首先把所有可能的長寬高都儲存起來,然後再對該數組求一個最長有序子序列即可!
隻要了解了什麼是最長有序子序列,那麼該題便迎刃而解!
代碼:
// Created by CAD on 2019/10/17.
#include <bits/stdc++.h>
using namespace std;
struct BOX{
int x,y;
int high,dp;
bool operator<(BOX &b)
{
if(x<b.x) return true;
return x==b.x && y<b.y;
}
}box[200];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,Case=0;
while(cin>>n,n)
{
int cnt=0;
for(int i=1;i<=n;++i)
{
int x,y,z; cin>>x>>y>>z;
box[++cnt].x=x,box[cnt].y=y,box[cnt].high=box[cnt].dp=z;
box[++cnt].x=x,box[cnt].y=z,box[cnt].high=box[cnt].dp=y;
box[++cnt].x=y,box[cnt].y=x,box[cnt].high=box[cnt].dp=z;
box[++cnt].x=y,box[cnt].y=z,box[cnt].high=box[cnt].dp=x;
box[++cnt].x=z,box[cnt].y=x,box[cnt].high=box[cnt].dp=y;
box[++cnt].x=z,box[cnt].y=y,box[cnt].high=box[cnt].dp=x;
}
sort(box+1,box+cnt+1);
int ans=0;
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
{
if(box[i].x>box[j].x&&box[i].y>box[j].y)
box[i].dp=max(box[j].dp+box[i].high,box[i].dp);
ans=max(ans,box[i].dp);
}
cout<<"Case "<<++Case<<": maximum height = "<<ans<<endl;
}
return 0;
}