Description
有n(n<=30)種立方體，每種都有無窮多個。要求選一些立方體摞成一根盡量高的柱子(可以自行選擇哪一邊作為高)，使得每個立方體的底面長寬分别嚴格小于它下方立方體的底面長度。
Inout sample
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
Output sample
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342
————————————————分割の線————————————————
分析
根據題意，上方立方體的底面積應當小于下方立方體的底面積，又因為每個立方體有無數個，是以可以得到一條結論
一個立方體下方的擺放不影響其上方的立方體擺放。
由此可以設f[i][j]表示到立方體i時以第j條邊作為高所能達到的最高值。(a[i][j]表示第i個立方第j條邊的高度)
于是就開始了對于狀态轉移方程的苦思冥想，
……
……
果然還是用記憶化搜尋更簡單
代碼如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[][],n;//f[i][j]表示以第i個立方體為底以第j條邊為高的最大高度
int a[][],cnt=;
int dp(int u,int hight)
{
if(f[u][hight]>=) return f[u][hight];
f[u][hight]=a[u][hight];//高至少為自己
int x,y,ux,uy;//x,y為第u個立方體的長和寬
if(hight==)
x=a[u][],y=a[u][];
if(hight==)
x=a[u][],y=a[u][];
if(hight==)
x=a[u][],y=a[u][];
for(int i=;i<=n;i++)
for(int k=;k<;k++)
{//ux,uy為第i個立方體的長和寬
if(k==)
ux=a[i][],uy=a[i][];
if(k==)
ux=a[i][],uy=a[i][];
if(k==)
ux=a[i][],uy=a[i][];
if(x>ux&&y>uy||y>ux&&x>uy)//如果滿足長和寬嚴格小于的這個基本事實，則向下進行搜尋
if(f[u][hight]<dp(i,k)+a[u][hight])
f[u][hight]=a[u][hight]+dp(i,k);//保留最佳答案
}
return f[u][hight];
}
int main()
{
scanf("%d",&n);
while(n>)//如果n不為0，則再次循環
{
cnt++;//記錄循環次數
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i][],&a[i][],&a[i][]);//讀入三條邊
memset(f,-,sizeof(f));//初始化f，預設f未做過
for(int i=;i<=n;i++)
for(int k=;k<;k++)
{
f[i][k]=dp(i,k);//請完成第一步，剩下的都交給記憶化搜尋吧
}
int ans=;
for(int i=;i<=n;i++)
for(int k=;k<;k++)
if(f[i][k]>ans) ans=f[i][k];//無腦枚舉，求最大值
printf("Case %d: maximum height = %d\n",cnt,ans);//按規則輸出答案
scanf("%d",&n);//再次讀入n
}
return ;
}