首页 > 代码库 > ZOJ1093 Monkey and Banana 【DP】
ZOJ1093 Monkey and Banana 【DP】
一、题目
ZOJ 1093
二、题目源程序
#include <stdio.h>//一个箱子有3种h..所以总共有3*n种高度.按面积从大到小排序#include <stdlib.h>struct block{ int x,y,z,h;}a[200];int cmp(const void *a,const void *b)//快排,模版{ return ((struct block *)b)->x*((struct block *)b)->y - ((struct block *)a)->x*((struct block *)a)->y;}int main(){ int b,c,d; int n,max,maxmax,k=0; int i,j; while(scanf("%d",&n)!=EOF && n) { k++; j=0; for(i=0;i<n;i++) { scanf("%d%d%d",&d,&b,&c);//用d,b,c防止后面把前面覆盖。 a[j].x=d;a[j].y=b;a[j++].z=c; a[j].x=d;a[j].y=c;a[j++].z=b; a[j].x=b;a[j].y=d;a[j++].z=c; a[j].x=b;a[j].y=c;a[j++].z=d; a[j].x=c;a[j].y=b;a[j++].z=d; a[j].x=c;a[j].y=d;a[j++].z=b; } qsort(a,6*n,sizeof(a[0]),cmp); for(i=0;i<n;i++) a[i].h=a[i].z; maxmax=a[0].h; for(i=0;i<6*n;i++) { max=a[i].z; for(j=0;j<i;j++) { if(a[i].x<a[j].x&&a[i].y<a[j].y) { if(a[i].z+a[j].h>max)//不重复加 max=a[i].z+a[j].h; } } a[i].h=max; if(a[i].h>maxmax) maxmax=a[i].h; } printf("Case %d: maximum height = %d\n",k,maxmax); } return 0;}
三、解题思路
1. 结构体利用 qsort() 函数排序。
2. 简单的动态规划问题。
四、心得体会
虽然这道题属于动态规划里的超基础水题,可是这是我做的第一道DP题目,花费了很长时间,都没有做出来。
最后看了大神的博客,才终于把它AC掉。
DP是很重要、占很大比重的一部分,一定要多做题!!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。