HDU/HDOJ 1069 Monkey and Banana

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1069

DP~~~

感觉有点类似二维的LIS。

好久没做题了，发现自己变水了很多，今天中午到的家，大概住20天~1个月吧，现在HDOJ的AC量是320，希望返校前能达到500，当然，如果仅此任务还不算很难，可是还有其他很多要学的，所以尽力吧。

代码：

#include 
#include 
using namespace std;

typedef struct Block{
    int l;    // 长
    int w;    // 宽
    int h;    // 高
    int sum;  // 当前最长长度
}Block;

int n;
Block nBlocks[100];
int cnt = 0;

// 按升序排列
bool cmp(Block m, Block n)
{
    return (m.l*m.w < n.l*n.w);
}

// 如果n放m上面
bool isOK(Block m, Block n)
{
    return (m.l>n.l && m.w>n.w) || (m.l>n.w && m.w>n.l); 
}

int main()
{
    freopen("input.txt", "r", stdin);
    int a, b, c;
    int temp;
    while(scanf("%d", &n;))
    {
        //cout << "n = " << n << endl;
        if(n == 0)
            break;
        ++cnt;
        for(int i=0; i<3*n; ++i)
        {
            scanf("%d %d %d", &a;, &b;, &c;);
            //cout << a << " " << b << " " << c << endl;
            nBlocks[i].l=a, nBlocks[i].w=b, nBlocks[i].h=c, ++i;
            nBlocks[i].l=b, nBlocks[i].w=c, nBlocks[i].h=a, ++i;
            nBlocks[i].l=c, nBlocks[i].w=a, nBlocks[i].h=b;
        }

        sort(nBlocks+0, nBlocks+3*n, cmp);
        //for(int i=0; i<3*n; ++i)
        //   cout << nBlocks[i].l << " " << nBlocks[i].w << " " << nBlocks[i].h << " " << nBlocks[i].l*nBlocks[i].w << endl;

        nBlocks[0].sum = nBlocks[0].h;
        for(int i=1; i<3*n; ++i)
        {
            temp = 0;
            for(int j=0; jtemp && isOK(nBlocks[i], nBlocks[j]))
                    temp = nBlocks[j].sum;
            }
            nBlocks[i].sum = temp + nBlocks[i].h;
        }
        temp = 0;
        for(int i=0; i<3*n; ++i)
        {
            if(nBlocks[i].sum > temp)
                temp = nBlocks[i].sum;
        }
        printf("Case %d: maximum height = %d\n", cnt, temp);
    }
    return 0;
}