Monkey and Banana（HDU 1069）解题报告（DP - 滚动数组）
一、原题
Monkey and Banana
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.
The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.
They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.
Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.
Input
The input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height".
Sample Input
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
Sample Output
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342
二、题目大意：
现在给你n“种”积木块（每种积木块无限个），每种积木块包含三个参数：
typedef struct
{
int x;
int y;
int z;
} Block;
现在要求将这些积木块叠放起来（必须保证两个积木块之间有缝隙），求最高的叠放高度
（类似于求最大递增子序列）
三、基本思路：
1、首先保证输入时，所有的x必须小于y（非常重要否则WA无数次）
接着把所有3*N个积木按照x，y从大到小排序
DP部分：
状态转移方程：dp[i]=max+blocks[i].z (max是所有可以放在i积木下的积木组合中最高的一个)
（1）将所有初始化为z（WA无数次）
for(int i=1; i<=3*n; i++)
dp[i]=blocks[i].z;
（2）i为当前求解项，j表示可以放在它下面的积木块下标，内层循环每次找到一个可以放在下面的“积木组合”放在当前项下方
for(int i=1; i<=3*n; i++)
{
for(int j=i-1; j>=1; j--)
{
if(ok(blocks[j],blocks[i])&&(dp[j]+blocks[i].z>dp[i]))
dp[i]=dp[j]+blocks[i].z;
}
if(dp[i]>ans) ans=dp[i];
}
Ps：这个过程相当于，将可以放在i以下的积木j=i-1~1的所有积木自底而上进行组合
2、最后从所有的dp[i]中挑选出最大的一个作为结果。
3、主要的变量：
Block blocks[N];//积木结构数组
int dp[NUM_BLOCK];//存储到第i个积木处的最大高度（在所有积木已经按照面积从大到小排序之后的情况下）
四、源码完整版
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NUM_BLOCK 100010
#define N 1000
using namespace std;
typedef struct
{
int x;
int y;
int z;
} Block;
Block blocks[N];
int dp[NUM_BLOCK];
inline bool ok(Block b1,Block b2)//这里必须严格递增
{
if(b1.x>b2.x&&b1.y>b2.y)//||(b1.y>b2.x&&b1.x>b2.y)
return true;
else
return false;
}
bool cmp(Block b1,Block b2)
{
if(b1.x==b2.x)
return b1.y>b2.y;
return b1.y>b2.y;
}
int main()
{
int n,ca=1;
///freopen("in.txt","r",stdin);
while(cin>>n&&n)
{
int tmp[3];
memset(blocks,0,sizeof(blocks));
memset(tmp,0,sizeof(tmp));
for(int i=1; i<=3*n; i+=3) //构造3*n个积木种类
{
cin>>tmp[0]>>tmp[1]>>tmp[2];
sort(tmp,tmp+3);
blocks[i].x=tmp[0];
blocks[i].y=tmp[1];
blocks[i].z=tmp[2];
blocks[i+1].x=tmp[0];
blocks[i+1].y=tmp[2];
blocks[i+1].z=tmp[1];
blocks[i+2].x=tmp[1];
blocks[i+2].y=tmp[2];
blocks[i+2].z=tmp[0];
}
sort(blocks+1,blocks+3*n+1,cmp);
int ans=0;
for(int i=1; i<=3*n; i++)
{
dp[i]=blocks[i].z;
}
for(int i=1; i<=3*n; i++)
{
for(int j=i-1; j>=1; j--)
{
if(ok(blocks[j],blocks[i])&&(dp[j]+blocks[i].z>dp[i]))
{
dp[i]=dp[j]+blocks[i].z;
}
}
if(dp[i]>ans) ans=dp[i];
}
cout<<"Case "<<ca++<<": maximum height = "<<ans<<endl;
}
return 0;
}
另，附上链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1069