HDU/HDOJ 1069 Monkey and Banana

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

DP~~~

感觉有点类似二维的LIS。

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <algorithm>
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; j<i; ++j)
            {
                if(nBlocks[j].sum>temp && 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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1069 Monkey and Banana》有35个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注