HDU 1069 Monkey and Banana (简单dp)

2018-03-31

Monkey and Banana

题意

有一些方块，三维属性x，y，z，每一块方块都有无限个，求这些方块堆起来能达到的最高海拔？

（下面的方块的x，y必须严格大于上面的x，y（对应））

<br>

思路

简单dp，由于方块有无限个，就让一个方块一次存6种可能的摆放方式，dp表示这个方块加上它下面的方块能达到的最大高度。

我按照x，y，z的降序排序，两重for循环中，因排序的不同而写的略微有差别，我的意思是a[i]在下，a[j]在上面的话，即满足a[i].x>a[j].x&&a[i].y>a[j].y , a[j].dp = max(a[j].dp, a[i].dp+a[j].z) ，就是说dp的是小方块。没错。嗯。

看！代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;
    int high;
};
bool cmp(node a,node b)
{
    if(a.x==b.x)
    {
        if(a.y==b.y)
            return a.z>b.z;
        return a.y>b.y;
    }
    return a.x>b.x;
}
int main()
{
    int n,cas=1;
    int x,y,z;
    while(~scanf("%d",&n)&&n)
    {
        node a[10010];
        int index=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[index].x=x;a[index].y=y;a[index].z=a[index].high=z;index++;
            a[index].x=x;a[index].y=z;a[index].z=a[index].high=y;index++;
            a[index].x=y;a[index].y=x;a[index].z=a[index].high=z;index++;
            a[index].x=y;a[index].y=z;a[index].z=a[index].high=x;index++;
            a[index].x=z;a[index].y=y;a[index].z=a[index].high=x;index++;
            a[index].x=z;a[index].y=x;a[index].z=a[index].high=y;index++;
        }
        sort(a,a+index,cmp);
        for(int i=0;i<index;i++)
            for(int j=i+1;j<index;j++)
                if(a[i].x>a[j].x&&a[i].y>a[j].y)
                    a[j].high=max(a[j].high,a[i].high+a[j].z);
        int ans=-1;
        for(int i=0;i<index;i++)
            ans=max(ans,a[i].high);
        printf("Case %d: maximum height = %d\n",cas++,ans);
    }
    return 0;
}