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]); }