大连企业免费建站/唐山seo排名

题意：有n种立方体，每种无穷个。要求选一些立方体摞成一根尽量高的柱子，使得每个立方体的底面长宽严格小于它下方立方体的底面长宽

解析：实际上每种立方体只有三次使用机会，先做预处理，给n*3种立方体编号。因为是严格小于的，所以这个图是DAG，可以套用DAG最长算法。建图，G[i][j]表示i到j有一条连线，j在i的上方。d[i]表示以i为起点的最长高度。对于底面长宽最大的立方体来说，以它为起点的长度就是这个立方体的高度，所以直接赋值。之后将每个点遍历一次。

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
int G[100][100];
long long d[100];//d[i]表示以i为起点的最大高度
struct node
{int w,l,h;
}q[100];
void init(int j,int w,int l,int h)
{q[j].w=max(w,l);q[j].l=min(w,l);q[j].h=h;
}
void comp(int i)//i在j的下面
{for(int j=0;j<i;j++){if(q[j].w<q[i].w&&q[j].l<q[i].l)//小的在后面G[i][j]=1;else if(q[j].w>q[i].w&&q[j].l>q[i].l)G[j][i]=1;}
}
long long int dp(int S)
{long long & ans=d[S];if(d[S]!=0)return d[S];for(int i=0;i<n*3;i++){if(G[i][S]!=0)ans=max(ans,dp(i)+q[S].h);}return ans;
}
int main()
{int h,w,l,num=0;while(scanf("%d",&n)&&n!=0)//{memset(G,0,sizeof(G));for(int i=0;i<n;i++){scanf("%d %d %d",&h,&w,&l);init(i*3,h,w,l);init(i*3+1,h,l,w);init(i*3+2,w,l,h);comp(i*3);comp(i*3+1);comp(i*3+2);//printf("-\n");}memset(d,0,sizeof(d));for(int i=0;i<n*3;i++)//找到值最大的点{int j;for(j=0;j<n*3;j++)if(G[j][i]!=0)break;if(j>=n*3){d[i]=q[i].h;//不止一个最大点}}long long ans=0;for(int j=0;j<n*3;j++)ans=max(ans,dp(j));num++;printf("Case %d: maximum height = %lld\n",num,ans);}return 0;
}

另外还看到一种方法是当做最长上升子序列，按六种式样预处理标号后，按照面积大小排序，之后用递推。关键思路是面积小的话是不可能排下面的，所以可以对所有面积较小的只遍历一次就可以了

1.  for(int i=0;i<m;i++)  
2.   {  
3.           dp[i]=node[i].z;  
4.           for(int j=0;j<i;j++)  
5.           {  
6.                if(node[i].x>node[j].x&&node[i].y>node[j].y)  
7.                {  
8.                     dp[i]=max(dp[i],dp[j]+node[i].z);  
9.                }  
10.            }  
11.            if(dp[i]>maxlen) maxlen=dp[i];  
12.   }