DP。
虽然说是很简单,但是花了我好多时间。。。。由于之前做DP的时候偷懒,省略了很多思维过程,所以这次格外的久。。。
说下我自己存在的问题。第一是建立方程的时候不知道要以什么标准来建立。
第二是状态转移方程。就算是看到了别人的方程,也会疑惑为什么这个过程是由这两部分构成的。刚开始的时候我想的是建立dp[i][j]=k,i是当前盒子的长,j是当前盒子的宽,k是当前的高度。然后就不知道怎么办了,感觉方程写不出来。。。结果题解就是很简单的DP[i]。
还有就是方程的实行。感觉每次这种事情都要在我脑海里物象化后才可以写出来。
好渣,继续努力。
**********************************
题意:给你n种盒子,然后你要叠盒子,下层的盒子一定要严格大于上层的盒子(长,宽),求可以堆的最大高度。
每个盒子可以把它变成六种盒子,各种姿势放到。然后进行堆叠。
原先以为对于j来说是把比他小的i放到上方,但是这样的话下次找比他更小的时候就很不好比较,所以这样的操作要归到最上方的那个盒子哪里去,也就是归到i的盒子组成上。
#include <stdio.h> #include <iostream> #include <algorithm> #include <cstring> using namespace std; #define maxn 1000 struct node { int x,y,z; }box[maxn*3]; int dp[maxn*3]; int max(int x,int y) { if(x>y) return x; else return y; } int cmp(node a,node b) { if(a.x!=b.x) return a.x>b.x; if(a.y!=b.y) return a.y>b.y; return a.z>b.z; } int main() { int cas=0; while(1) { int n; scanf("%d",&n); if(!n) break; int i,j,k; int a,b,c; int top=0; for(i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); //变形 box[top].x=b;box[top].y=a;box[top].z=c; top++; box[top].x=a;box[top].y=c;box[top].z=b; top++; box[top].x=c;box[top].y=b;box[top].z=a; top++; box[top].x=c;box[top].y=a;box[top].z=b; top++; box[top].x=a;box[top].y=b;box[top].z=c; top++; box[top].x=b;box[top].y=c;box[top].z=a; top++; } sort(box,box+6*n,cmp); int ans=-1; for(i=0;i<6*n;i++) { int tmp=-1; dp[i]=box[i].z; for(j=0;j<i;j++) if(box[j].x>box[i].x&&box[j].y>box[i].y&&tmp<dp[j]) //在i前面找比他大的符合题意的盒子,然后把它垫到底下。 tmp=dp[j]; if(tmp>0) dp[i]+=tmp; ans=max(ans,dp[i]); } printf("Case %d: maximum height = %d\n",++cas,ans); } return 0; }