我相信伴奏,疯果网,安全教育手抄报
c - monkey and banana
time limit:1000ms memory limit:32768kb 64bit io format:%i64d & %i64u
submit status practice hdu 1069case 4: maximum height = 342
刚开始学动态规划,还是挺难的,我参考了这位大神的思路
dp[i]:表示以p[i]这个长方体放在顶端,可以获得最大的高度。
那么状态转移是,dp[i]=max( dp[i], p[i].high + dp[j] )
#include #include #include #include #include #include using namespace std; templateinline t read(t&x) { char c; while((c=getchar())<=32)if(c==eof)return 0; bool ok=false; if(c=='-')ok=true,c=getchar(); for(x=0; c>32; c=getchar()) x=x*10+c-'0'; if(ok)x=-x; return 1; } template inline t read_(t&x,t&y) { return read(x)&&read(y); } template inline t read__(t&x,t&y,t&z) { return read(x)&&read(y)&&read(z); } template inline void write(t x) { if(x<0)putchar('-'),x=-x; if(x<10)putchar(x+'0'); else write(x/10),putchar(x%10+'0'); } templateinline void writeln(t x) { write(x); putchar('\n'); } //-------zcc io template------ const int maxn=400; const double inf=999999999; #define lson (rt<<1),l,m #define rson (rt<<1|1),m+1,r #define m ((l+r)>>1) #define for(i,t,n) for(int i=(t);i<(n);i++) typedef long long ll; typedef double db; typedef pair p; #define bug printf("---\n"); #define mod 1000000007 struct node { int width,length,area,high; bool operator<(const node&a) const { return area>a.area; } }p[maxn]; int dp[maxn]; int main() { int n,m,i,j,t,k; int cas=1; while(read(n)&&n) { k=0; for(i,0,n) { int w,l,h; read__(w,l,h); node tmp; tmp.width=w;tmp.length=l;tmp.high=h; tmp.area=w*l; p[k++]=tmp; tmp.width=w;tmp.length=h;tmp.high=l; tmp.area=w*h; p[k++]=tmp; tmp.width=h;tmp.length=l;tmp.high=w; tmp.area=h*l; p[k++]=tmp; } sort(p,p+k); dp[0]=p[0].high; for(i=1;ip[i].width&&p[j].length>p[i].length||p[j].width>p[i].length&&p[j].length>p[i].width) { dp[i]=max(dp[i],dp[j]+p[i].high); } } // for(i,0,k) // printf("dp[%d] = %d\n",i,dp[i]); printf("case %d: maximum height = %d\n",cas++,*max_element(dp,dp+k)); } return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论