HDU 1069 Monkey and Banana DP LIS

http://acm.hdu.edu.cn/showproblem.php?pid=1069

题目大意

一群研究员在研究猴子的智商(T T禽兽啊，欺负猴子！！！），他们决定在房顶放一串香蕉，并且给猴子n种砖块。

砖块长宽高分别为xyz，每一种可以取任意个，并且他们可以随意的摆放。

然后要求堆叠起来的砖块上面的必须严格小于下面的。

求最大可以堆叠的高度。

思路：

转化为LIS问题，把每一种摆放方法如（10,20,30）（可以以20 30 作为底，10作为高）都放进数组，然后就是求最大上升子序列。

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=200;

struct data

{

    int x,y;

    int h;

}a[MAXN];

bool operator <(const data &a,const data &b)

{

    return a.x<b.x;

}

int main()

{

    int n;

    int kase=1;

    while(scanf("%d",&n),n)

    {

        int len=0;

        int x,y,z;

        for(int i=0;i<n;i++)

        {

            scanf("%d%d%d",&x,&y,&z);

            a[len].x=x;    a[len].y=y;     a[len++].h=z;

            a[len].x=x;    a[len].y=z;     a[len++].h=y;

            a[len].x=y;    a[len].y=x;     a[len++].h=z;

            a[len].x=y;    a[len].y=z;     a[len++].h=x;

            a[len].x=z;    a[len].y=x;     a[len++].h=y;

            a[len].x=z;    a[len].y=y;     a[len++].h=x;

        } 

        sort(a,a+len);

        int dp[MAXN];

        for(int i=0;i<len;i++)

        {

            dp[i]=a[i].h;

            int temp=0;

            for(int j=0;j<i;j++)

            {

                if(a[i].x>a[j].x && a[i].y >a[j].y)

                    temp=max(temp,dp[j]);

            }

            dp[i]+=temp;

        }

        int ans=0;

        for(int i=0;i<len;i++)

            ans=max(ans,dp[i]);

        printf("Case %d: maximum height = %d\n",kase++,ans);

    }

    return 0;

}

巴特西

HDU 1069 Monkey and Banana DP LIS

最新文章

热门文章