HDU 1069 Monkey and Banana(最长递减子序列)

题意：摞长方体，给定长方体的长宽高，个数无限制，可随意翻转，要求下面的长方体的长和宽都大于上面的，都不能相等，问最多能摞多高。

题解：个数无限，其实每种形态最多就用一次，把每种形态都单独算一种，同时保证长比宽大，按dp做即可。注意要从小到大摞，从大到小是不对的。

#include <bits/stdc++.h>

using namespace std;

struct sa

{

    int l,w,h;

}data[];

int dp[],n,d[];

bool cmp(sa x,sa y)

{

    if(x.l==y.l) return x.w<y.w;

    return x.l<y.l;

}

int main()

{

    int t=;

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

    {

        int cnt=;

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

        {

            scanf("%d%d%d",&d[],&d[],&d[]);

            sort(d,d+);

            data[cnt].l=d[],data[cnt].w=d[],data[cnt].h=d[],cnt++;

            data[cnt].l=d[],data[cnt].w=d[],data[cnt].h=d[],cnt++;

            data[cnt].l=d[],data[cnt].w=d[],data[cnt].h=d[],cnt++;

        }

        sort(data,data+cnt,cmp);

        for(int i=;i<cnt;i++)

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

        for(int i=;i<cnt;i++)

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

        {

            if(data[j].l<data[i].l&&data[j].w<data[i].w)

            {

                if(dp[i]<dp[j]+data[i].h)//双层for更直观

                    dp[i]=dp[j]+data[i].h;

            }

        }

        int ans=dp[];

        for(int i=;i<cnt;i++)

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

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

    }

    return ;

}

传送门：http://blog.csdn.net/qinmusiyan/article/details/7986263

巴特西

HDU 1069 Monkey and Banana(最长递减子序列)

最新文章

热门文章