Problem
acm.hdu.edu.cn/showproblem.php?pid=1069
Reference
www.cnblogs.com/kuangbin/archive/2011/08/04/2127291.html
题意
给 n 种块,每种无限多个,求能搭起来的最高的高度。
每种块都是长方体,给出三维(x,y,z),每个块都可以任选一个面做底面。
一个块能放在另一个块上面,当且仅当上面的块的底面的两维都分别 严格小于 下面的块的底面的两维。(最下面是地面,无限大)
Analysis
每种块分别选它的三维当高,能摆出三种(因为数量少,有重复也不考虑去重,好写)。当选了一维当高以后,约定:剩下的两维中较短的为宽,较长的为长。
开始想到的DP方案是:dp[i][j][k]:用前 i 种块,当前底面为 j * k 时的最高高度
转移方程:dp[i][j][k] = max { dp[i][j][k], dp[i-1][ block [i].width ][ block [i].length ] + block [i].height }
在输入完后,要加多一个底面两维比所有块的三维的长度都要长、高为 0 的虚块,当作地面。
但因为题目没给出三个维度的长度的范围,数组大小不好估计,所以开大了会MLE,开小了会数组越界。而且就算给了范围,只要范围大些就开不了那么大的数组。
于是换一种方案:dp[i]:最下面放第 i 种块的时候能搭出的最高高度
状态转移:dp[i] = max { dp[j] + block [i].height | block [j].width < block [i].width && block [j].length < block [i].length }
Source code
1. MLE / RE (ACCESS_VIOLATION )
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int LEN = 10000, N = 30;
struct block
{
int x, y, z; // x: width, y: length, z: height
block() {}
block(int _x, int _y, int _z): z(_z)
{
if(_x > _y)
x = _y, y = _x;
else
x = _x, y = _y;
}
} b[N*3];
int dp[LEN+2][LEN+2];
int main()
{
int n;
for(int kase=1, big=0, top=0; scanf("%d",&n),n; ++kase, big=top=0)
{
for(int i=0, x, y, z; i<n; ++i)
{
scanf("%d%d%d", &x, &y, &z);
b[top++] = block(x, y, z);
b[top++] = block(x, z, y);
b[top++] = block(y, z, x);
big = max(max(big, x), max(y, z));
}
++big; // 比最大的长度还要大1,保证放得下最大的底面
memset(dp, 0, sizeof dp);
for(int l=1; l<=big; ++l)
for(int w=1; w<=l; ++w)
for(int i=0; i<top; ++i)
if(b[i].x<w && b[i].y<l)
dp[w][l] = max(dp[w][l],
dp[b[i].x][b[i].y] + b[i].z);
printf("Case %d: maximum height = %d\n", kase, dp[big][big]);
}
return 0;
}
2. Accepted
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
struct block
{
int x, y, z, dp;
block() {}
block(int _x, int _y, int _z): z(_z), dp(_z)
{
if(_x < _y)
x = _x, y = _y;
else
x = _y, y = _x;
}
bool operator < (const block &bk) const
{
return x < bk.x && y < bk.y;
}
} b[N*3+1];
inline bool cmp(const block &a, const block &b)
{
return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
int main()
{
ios::sync_with_stdio(false);
for(int n, kase=1; cin>>n, n; ++kase)
{
int big = 0;
for(int i=0, j=0, x, y, z; i<n; ++i)
{
cin >> x >> y >> z;
b[j++] = block(x, y, z);
b[j++] = block(y, z, x);
b[j++] = block(z, x, y);
big = max(max(big, x), max(y, z));
}
b[3*n] = block(big, big, 0);
sort(b, b+3*n+1, cmp);
int ans = 0;
for(int i=1; i<=3*n; ++i)
{
for(int j=0; j<i; ++j)
if(b[j] < b[i])
b[i].dp = max(b[i].dp,
b[j].dp + b[i].z);
ans = max(ans, b[i].dp);
}
cout << "Case " << kase << ": maximum height = " << ans << '\n';
}
return 0;
}