商丘网站推广渠道,有经验的聊城网站建设,浅谈电子商务网站建设与管理,网站 开发 备案代理题意#xff1a;给定n个长方体#xff0c;然后堆积最高的塔#xff0c;要求上面的面积小于下面的面积。 思路#xff1a;Dp#xff0c;先把长方体的所有放的情况都构造出来放到数组里#xff0c;对于当前节点#xff0c;如果能够在前面找到面积比当前小#xff0c;高度…
题意给定n个长方体然后堆积最高的塔要求上面的面积小于下面的面积。 思路Dp先把长方体的所有放的情况都构造出来放到数组里对于当前节点如果能够在前面找到面积比当前小高度累加比当前高的则转移状态。 code #include bits/stdc.h
using namespace std;#define ft(i,s,t) for(int is;it;i)const int N95;
struct node
{int x,y,h;
}g[N];
int dp[N],v[3];bool cmp(node a,node b){if (a.xb.x) return a.yb.y;return a.xb.x;
}
int main()
{int n,ca1;while(~scanf(%d,n),n){int l0;ft(j,0,n-1){ft(i,0,2) scanf(%d,v[i]);sort(v,v3);ft(i,0,2){g[li].hv[(0i)%3];g[li].xv[(2i)%3];g[li].yv[(1i)%3];}swap(g[l1].x,g[l1].y);l3;}sort (g,gl,cmp);int ans0;ft(i,0,l-1){dp[i]g[i].h;for (int j0;ji;j){if (g[j].xg[i].xg[j].yg[i].ydp[i]dp[j]g[i].h)dp[i]dp[j]g[i].h;}ansmax(ans,dp[i]);}printf(Case %d: maximum height %d\n,ca,ans);}
}
