hdu 1069 Monkey and Banana（动态规划）

第一遍是用递归写的，测试过了，但是提交后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; }