【DP】Leo搭积木(brick)

本文主要是介绍【DP】Leo搭积木(brick)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$Description$

Leo是一个快乐的火星人，总是能和地球上的OIers玩得很high。
2012到了，Leo又被召回火星了，在火星上没人陪他玩了，但是他有好多好多积木，于是他开始搭积木玩。
火星人能制造n种积木，积木能无限供应。每种积木都是长方体，第i种积木的长、宽、高分别为li、wi、hi。积木可以旋转，使得长宽高任意变换。Leo想要用这些积木搭一个最高的塔。问题是，如果要把一个积木放在另一个积木上面，必须保证上面积木的长和宽都严格小于下面积木的长和宽。这意味着，即使两块长宽相同的积木也不能堆起来。
火星上没有电脑，好心的你决定帮助Leo求出最高的塔的高度。

$Input$

第一行，一个整数n，表示积木的种数
接下来n行，每行3个整数li，wi，hi，表示积木的长宽高

$Output$

一行一个整数，表示塔高的最大值

$Sample$ $Input$#$1$

1
10 20 30

$SampleInput$#$2$

2
6 8 10
5 5 5
1
2
3

$Sample$ $Input$#$3$

5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
1
2
3
4
5
6

$Sample$ $Output$#1

40
1

$Sample$ $Output$#$2$

21
1

$Sample$ $Output$#$3$

3427087

思路

一个方块
旋转可以得到六种方块
如果要满足长一定大于宽
那就可以缩成三种
然后对其进行排序
最后DP最长单调下降序列

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct brick
{int l, w, h;
}A[1000250];
int Sum, n, k, x, y, z;
int Ans[1000250];
bool Nm(brick i, brick j)
{if(i.l != j.l)return i.l > j.l;return i.w > j.w;
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%d%d%d", &x, &y, &z);A[++k] = (brick) {max(x, y), min(x, y), z};A[++k] = (brick) {max(y, z), min(y, z), x};A[++k] = (brick) {max(x, z), min(x, z), y};}sort(A + 1, A + k + 1, Nm);for(int i = 1; i <= k; ++i){for(int j = i - 1; j >= 0; --j)if(A[i].l < A[j].l && A[i].w < A[j].w)Ans[i] = max(Ans[i], Ans[j]);Ans[i] += A[i].h;Sum = max(Sum, Ans[i]);}printf("%d", Sum);return 0;
}

这篇关于【DP】Leo搭积木(brick)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---