hdu 1069 Monkey and Banana（动态规划）

2019-11-06 06:29:56

字体：大中小

来源：转载

供稿：网友

第一遍是用递归写的，测试过了，但是提交后tle了，然后怎么也没能改成dp的代码。。。参考了下别人的代码：http://blog.csdn.net/wyg1997/article/details/52254176 思路还是很简单的

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{ int x,y,height;};int len;node block[200];int dp[200];int res;bool cmp(node &a, node &b){ if(a.x == b.x) return a.y > b.y; return a.x > b.x;}int main(){ int n,x,y,z,time = 0; while(scanf("%d",&n) && n) { ++time; len = 0; res = 0; //每一块都有六个情况 for(int i = 0; i < n; ++i) { scanf("%d %d %d",&x,&y,&z); block[len].x = x; block[len].y = y; block[len].height = z; ++len; block[len].x = y; block[len].y = x; block[len].height = z; ++len; block[len].x = x; block[len].y = z; block[len].height = y; ++len; block[len].x = z; block[len].y = x; block[len].height = y; ++len; block[len].x = y; block[len].y = z; block[len].height = x; ++len; block[len].x = z; block[len].y = y; block[len].height = x; ++len; } memset(dp,0,sizeof(dp)); sort(block,block+len,cmp); for(int i = 0; i < len; ++i) { //dp[i]表示前i块可以放的最大高度 //先直接放上第i块 dp[i] = block[i].height; for(int j = i-1; j >= 0; --j) { //如果第i块可以放在第j块上，则选择max(dp[i],block[i].height+dp[j]) if(block[i].x < block[j].x && block[i].y < block[j].y) { dp[i] = max(dp[i],block[i].height+dp[j]); } } res = max(res,dp[i]); } PRintf("Case %d: maximum height = %d/n",time,res); } return 0;}

上一篇：[ windows程序设计(programing windows) ] - 控制项之列表框扩展

下一篇：HPC-paperweekly-01（3月）