hdu 1069 Monkey and Banana (两种解法 1.dp 2.记忆化搜索)

Monkey and BananaTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6069 Accepted Submission(s): 3085

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define maxn 105using namespace std;int n,m,ans,cnt;int dp[maxn];struct Node{ int x,y,z;}q[maxn];int dfs(int pos){ if(dp[pos]!=-1) return dp[pos]; int i,j,nx,ny,ma; nx=q[pos].x; ny=q[pos].y; ma=0; for(i=1;i<=cnt;i++) { if(q[i].x<nx&&q[i].y<ny) ma=max(ma,dfs(i)); } dp[pos]=ma+q[pos].z; return dp[pos];}int main(){ int i,j,t,x[3],test=0; while(scanf("%d",&n),n) { cnt=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&x[0],&x[1],&x[2]); sort(x,x+3); q[++cnt].x=x[0],q[cnt].y=x[1],q[cnt].z=x[2]; // x、y需按顺序 WA了好多次 q[++cnt].x=x[1],q[cnt].y=x[2],q[cnt].z=x[0]; q[++cnt].x=x[0],q[cnt].y=x[2],q[cnt].z=x[1]; } ans=0; memset(dp,-1,sizeof(dp)); for(i=1;i<=cnt;i++) { t=dfs(i); if(ans<t) ans=t; } printf("Case %d: maximum height = %d\n",++test,ans); } return 0;}