题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1069
题意就是给你n种长方体每种类型不限制个数,然后我们把它们一个个堆起来,并且要满足下面的要比上面的大,不能相等,求最大能达到的高度;我们可以把这归为动态规划,求最长上升子序列的问题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define N 220
struct node
{
int x,y,z,v,h;
};
int cmp(node a,node b)
{ return a.v<b.v;
}
int main()
{
int i,j,x,y,z,n,t=;
node a[N];
while(scanf("%d",&n),n)
{
memset(a,,sizeof(a));
j=;
for(i=;i<n;i++)
{
scanf("%d %d %d",&x,&y,&z);
a[j].x=x;a[j].y=y;a[j].z=z;a[j].v=x*y;j++;
a[j].x=y;a[j].y=z;a[j].z=x;a[j].v=y*z;j++;
a[j].x=z;a[j].y=x;a[j].z=y;a[j].v=x*z;j++;
}
sort(a,a+j,cmp);
for(i=;i<n*;i++)
{
int MAX=;
for(j=;j<i;j++)
{
if(((a[i].x>a[j].y&&a[i].y>a[j].x)||(a[i].x>a[j].x&&a[i].y>a[j].y))&&a[j].h>MAX)
{
MAX=a[j].h;
}
}
a[i].h=a[i].z+MAX;
}
int ans=;
for(i=;i<*n;i++)
{
ans=max(ans,a[i].h);
}
t++;
printf("Case %d: maximum height = %d\n",t,ans);
}
return ;
}
后来又写了一遍…都差不多:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
#define N 1010
struct node
{
int x,y,w;
}a[N];int cmp(node p, node q)
{
if(p.x != q.x)
return p.x<q.x;
return p.y<q.y;
}int main()
{
int n, x, y, z, dp[N], t=;
while(scanf("%d", &n), n)
{
int k = ;
for(int i=; i<n; i++)
{
scanf("%d%d%d", &x, &y, &z);
if(x>y)swap(x, y);
if(x>z)swap(x, z);
if(y>z)swap(y, z);
a[k].x=x; a[k].y=y; a[k++].w=z;
a[k].x=x; a[k].y=z; a[k++].w=y;
a[k].x=y; a[k].y=z; a[k++].w=x;
}
sort(a, a+k, cmp);
memset(dp, , sizeof(dp));
int ans = ;
for(int i=; i<k; i++)
{
dp[i] = a[i].w;
for(int j=; j<i; j++)
{
if(a[i].x>a[j].x && a[i].y>a[j].y)
dp[i]=max(dp[i], dp[j]+a[i].w);
}
ans = max(ans, dp[i]);///dp[k-1]不一定是最大的;这是突然明白的-_-;
}
printf("Case %d: maximum height = %d\n", t++, ans);
}
return ;
}