hdu -Monkey and Banana 动态规划

Monkey and Banana

Problem 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

这道题是简单动规，但是我觉得和贪心实在太像了
搞的我又有点分不清贪心和动规了
思路
（1）输入问题；这不是普通的输入，因为一个长方体可以用多次
但是实际上最多用3次6个面两两重复（其实刚开始我还写的两个，因为我觉得一个长方体最大面和最小面能用一下，另一个面和最大面，最小面有一边相等，这样想是错误的）
（2）这样一个长方体变成3个长方体，选长方体使其最高，乍一看像背包，一件物品选或者不选，但是，天真的我忘了一点，背包选物品是没有顺序，这个物品可以放在最后判断选不选，也可以放在前面，但是这题不一样，先选和后选是不一样的，先选可能能选上，但是后选就不一定能不能选上了，这一点差别导致思想千差万别
（3）既然要取最大值，那么最好还是把最大的放后面，这样我们从头开始找（你是不是想到了贪心），但是贪心是做不好这道题的，
如果遇到相同的长（或者宽），那么你要选择哪一个？而且即使选择了最高的（假设是第一个，没选的是第二个），你能保证下一次不会出一个宽（或者长）比第一个长，比第二个短，而且高特别高；那么只能动态规划了，动态规划会记录前面所有的情况的最优解，用前面的多个选一个推出下一个，贪心只能用最近的一个推下一个
这就是动规和贪心的本质区别
这是我思考的思路，写出来供大家思考
下面是题的思路
（1）先输入后，一个变3个，然后排一下序，从大到小（这样方便）
（2）然后就是最长单调递减子序列
那么为什么会联系到最长单调递减子序列那？
对，我们排序后，长方体都从小到大排好序了，我们要找最高，那么其实我们就是把单调递减子序列的最多，换成了最高，

下面分析一下最长单调递减子序列的动态
其实说简单点就一句话；
从头开始遍历，每遍历一个，找找前面的，有没有比这个大的，如果有，那么找出一个结果最大的（即最优解）以这个为上一个状态，在这个状态上加上当前的值
这就是当前的最优解；
废话不多说，上代码

#include #include #include struct stu{ int x,y,z,h; }s[1000]; int cmp1(const void*a,const void*b) { return *(int *)b-*(int *)a; } int cmp2(const void*a,const void*b) { struct stu *c,*d; c=(struct stu*)a; d=(struct stu*)b; return d->x*d->y-c->x*c->y; } int main() { int n,i,a[3],m,max,j,q=1; ; while(scanf("%d",&n)!=-1,n) { memset(s,0,sizeof(s)); i=0; while(n--) { scanf("%d%d%d",&a[0],&a[1],&a[2]); qsort(a,3,sizeof(a[0]),cmp1); s[i].x=a[0]; s[i].y=a[1]; s[i++].z=a[2]; s[i].x=a[1]; s[i].y=a[2]; s[i++].z=a[0]; s[i].x=a[0]; s[i].y=a[2]; s[i++].z=a[1]; } m=i; qsort(s,m,sizeof(s[0]),cmp2); s[0].h=s[0].z; for(i=1; imax&&s[j].x>s[i].x&&s[j].y>s[i].y) max=s[j].h; } s[i].h=s[i].z+max; } max=0; for(i=0; imax) max=s[i].h; } printf("Case %d: maximum height = %d\n",q++,max); } return 0; }

总结；
通过这道题我又对动规有深入的了解了，动规其实是把好多个解存起来了，供你下次找最优解用，不是单纯的一个
如果是一个，那么你就做成贪心了，
对于动规；我们要做的就是考虑如何储存要用的最优解和如何利用前面求出来的最优解来更新当前最优解
【hdu -Monkey and Banana】