简单DP。
题意:给出若干种长方体,如果摆放时一个长方体的长和宽小于另一个的长宽,那么它可以放在另一个的上面,问最高能放多少高度。每种长方体的个数都是无限的。
做法:因为每种个数都是无限,那么每种按照x,y,z分别重新排列可以得到6种长方体。现在用dp[i]表示选到第i个且第i个必须使用的最大高度,那么转移是从1~i-1中的dp中选一个能放在i的前面的最大值放在i的前面,再加上第i个的高,就得到了dp[i](如果一个都不能放在i的前面,那就只放i即可)。然后最终答案是dp[1]~dp[n]的最大值。
注意点是在dp前必须按照(x,y)先排序,这样可以保证第i个能够放在它前面的一定在1~i-1中(后面的一定x或y比它大)。
代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
const int N = 1e7 + ;
const int inf = 0x3f3f3f3f; struct node
{
int x,y,z;
bool operator < (const node & temp) const
{
return x == temp.x ? y < temp.y : x < temp.x;
}
}p[]; int dp[]; int main()
{
int kase = ;
int n;
while(scanf("%d",&n) == && n)
{
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
p[i+n] = (node){p[i].x,p[i].z,p[i].y};
p[i+*n] = (node){p[i].y,p[i].x,p[i].z};
p[i+*n] = (node){p[i].y,p[i].z,p[i].x};
p[i+*n] = (node){p[i].z,p[i].x,p[i].y};
p[i+*n] = (node){p[i].z,p[i].y,p[i].x};
}
sort(p+,p++*n);
memset(dp,,sizeof dp);
for(int i=;i<=*n;i++)
{
dp[i] = p[i].z;
for(int j=;j<i;j++)
{
if(p[j].x < p[i].x && p[j].y < p[i].y && dp[j] + p[i].z > dp[i]) dp[i] = dp[j] + p[i].z;
}
}
printf("Case %d: maximum height = %d\n",kase++,*max_element(dp+,dp++*n));
}
}
顺便考虑一个问题,如果要求的是最大能放几个长方体,那就是LIS的问题了。