HDU 1069 Monkey and Banana

正文索引 [隐藏]

题目翻译
题解
代码

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

题目翻译

N种有长宽高的盒子（每个无限），堆起来，上面的盒子的底面必须严格小于下面的盒子的底面，求最高能够到达的高度。

题解

F[x,y]表示最上面的盒子的底面参数为x * y的盒子堆所能达到的最高高度。
然后直接暴力DP就好。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int Maxn=30;
struct Block
{
    int x, y, z;
    Block(){};
    Block(int x0, int y0, int z0)
    {
        x = x0;
        y = y0;
        z = z0;
    }
};
Block bl[Maxn+5];
int n;
map< pair<int,int>, int > DP, tmp;
inline void compareAns(int x, int y, int val)
{
    if (x > y) swap(x, y);
    pair<int, int> now = make_pair(x, y);
    DP[now] = max(DP[now], val);
}
inline void compare(pair<int, int>prev, int x, int y, int val)
{
    if (x > y) swap(x, y);
    pair<int, int> now = make_pair(x, y);
    if (prev.first >= now.first || prev.second >= now.second) return ;
    tmp[now] = max(tmp[now], val);
}
inline void solve(int T)
{
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &bl[i].x, &bl[i].y, &bl[i].z);
    DP.clear();
    for (int i = 1; i <= n; i++)
    {
        compareAns(bl[i].x, bl[i].y, bl[i].z);
        compareAns(bl[i].x, bl[i].z, bl[i].y);
        compareAns(bl[i].z, bl[i].y, bl[i].x);
    }
    for (int rt = 2; rt <= 3 * n; rt++)
    {
        tmp.clear();
        for (map< pair<int,int>, int >::iterator it = DP.begin(); it != DP.end(); it++)
        {
            //printf("Base : %d - %d -> Height = %d\n", (*it).first.first, (*it).first.second, (*it).second);
            for (int i = 1; i <= n ; i++)
            {
                compare((*it).first, bl[i].x, bl[i].y, (*it).second + bl[i].z);
                compare((*it).first, bl[i].z, bl[i].y, (*it).second + bl[i].x);
                compare((*it).first, bl[i].x, bl[i].z, (*it).second + bl[i].y);
            }
        }
        for (map< pair<int,int>, int >::iterator it = tmp.begin(); it != tmp.end(); it++)
        {
            DP[(*it).first] = max(DP[(*it).first], (*it).second);
        }
    }
    int Ans = 0;
    for (map< pair<int,int>, int >::iterator it = DP.begin(); it != DP.end(); it++)
    {
        Ans = max(Ans, (*it).second);
    }
    printf("Case %d: maximum height = %d\n", T, Ans);
}
int main()
{
    int T = 0;
    while(scanf("%d", &n) != EOF)
    {
        if (n==0) return 0;
        solve(++T);
    }
    return 0;
}

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<map>

using namespace std;

const int Maxn=30;

struct Block

{

int x, y, z;

Block(){};

Block(int x0, int y0, int z0)

{

x = x0;

y = y0;

z = z0;

}

};

Block bl[Maxn+5];

int n;

map< pair<int,int>, int > DP, tmp;

inline void compareAns(int x, int y, int val)

{

if (x > y) swap(x, y);

pair<int, int> now = make_pair(x, y);

DP[now] = max(DP[now], val);

}

inline void compare(pair<int, int>prev, int x, int y, int val)

{

if (x > y) swap(x, y);

pair<int, int> now = make_pair(x, y);

if (prev.first >= now.first || prev.second >= now.second) return ;

tmp[now] = max(tmp[now], val);

}

inline void solve(int T)

{

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

scanf("%d%d%d", &bl[i].x, &bl[i].y, &bl[i].z);

DP.clear();

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

{

compareAns(bl[i].x, bl[i].y, bl[i].z);

compareAns(bl[i].x, bl[i].z, bl[i].y);

compareAns(bl[i].z, bl[i].y, bl[i].x);

}

for (int rt = 2; rt <= 3 * n; rt++)

{

tmp.clear();

for (map< pair<int,int>, int >::iterator it = DP.begin(); it != DP.end(); it++)

{

//printf("Base : %d - %d -> Height = %d\n", (*it).first.first, (*it).first.second, (*it).second);

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

{

compare((*it).first, bl[i].x, bl[i].y, (*it).second + bl[i].z);

compare((*it).first, bl[i].z, bl[i].y, (*it).second + bl[i].x);

compare((*it).first, bl[i].x, bl[i].z, (*it).second + bl[i].y);

}

for (map< pair<int,int>, int >::iterator it = tmp.begin(); it != tmp.end(); it++)

{

DP[(*it).first] = max(DP[(*it).first], (*it).second);

}

int Ans = 0;

for (map< pair<int,int>, int >::iterator it = DP.begin(); it != DP.end(); it++)

{

Ans = max(Ans, (*it).second);

}

printf("Case %d: maximum height = %d\n", T, Ans);

}

int main()

{

int T = 0;

while(scanf("%d", &n) != EOF)

{

if (n==0) return 0;

solve(++T);

}

return 0;

}

一	二	三	四	五	六	日
						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

WNJXYKの博客

喂你脚下有坑