SSL-ZYC 堆箱子

本文主要是介绍SSL-ZYC 堆箱子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
小Z一堆箱子，每个箱子都有各自的长、宽、高，要求放在下面的箱子的长和宽都分别大于它上面的箱子的长和宽。现在他想知道他究竟能堆出多高的塔。 又由于箱子是长方体的，因此你可以把它随意转动，也就是说，它的长、宽、高是可以随意互换的。每种箱子的数量都可认为是无限个。请问最高能搭多高的塔？

---

思路：
一开始认为这是一道DFS的题目，因为实在没想到其他做法。但是后来发现会超时，所以最后用了一种神奇的DP做对了这道题。
由于每个箱子可以随意转动，所以每个箱子转动会得到6种不同的形状（除非它是正方体）。所以一开始我们读入的时候，就要用6*n的数组来储存箱子的每一种形状。
然后我们用快排，以箱子的长和宽来排序。最后用DP找出最高的高度。

状态转移方程：f[j]=max(f[j],f[i]+h[j]);

---

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1001],b[1001],h[1001],n,k,maxn,f[1001];void sorts(int l,int r)  //快排
{int i,j,z,p;i=l;j=r;z=a[(i+j)/2];p=b[(i+j)/2];do{while (a[i]>z||(a[i]==z&&b[i]>p)) i++;while (a[j]<z||(a[j]==z&&b[j]<p)) j--;if (i<=j){swap(a[i],a[j]);swap(b[i],b[j]);swap(h[i],h[j]);i++;j--;}}while(i<=j);if (i<r) sorts(i,r);if (j>l) sorts(l,j);
}
int main()
{freopen("boxes.in","r",stdin);freopen("boxes.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++){k=i*6-5;scanf("%d%d%d",&a[k],&b[k],&h[k]);a[k+1]=a[k]; b[k+1]=h[k]; h[k+1]=b[k];a[k+2]=b[k]; b[k+2]=a[k]; h[k+2]=h[k];a[k+3]=b[k]; b[k+3]=h[k]; h[k+3]=a[k];a[k+4]=h[k]; b[k+4]=a[k]; h[k+4]=b[k];a[k+5]=h[k]; b[k+5]=b[k]; h[k+5]=a[k];  //6种情况} n*=6;sorts(1,n);  //以长和宽来快排 for (int i=1;i<=n;i++) f[i]=h[i];for (int i=1;i<=n-1;i++)for (int j=i+1;j<=n;j++)if (a[i]>a[j]&&b[i]>b[j])f[j]=max(f[j],f[i]+h[j]);  //DP状态转移方程for (int i=1;i<=n;i++)maxn=max(maxn,f[i]);  //寻找最高高度printf("%d\n",maxn);return 0;
}

这篇关于SSL-ZYC 堆箱子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---