HDU 1069

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069

题意：把给定的长方体（不限）叠加在一起，叠加的条件是，上面一个长方体的长和宽都比下面长方体的长

和宽短；求这些长方体能叠加的最高的高度.（其中（3，2，1）可以摆放成（3，1，2）、（2，1，3）等）.

思路：其实就是求最长的单调递减序列。在长和宽的递减下，求最大能得出的最大高度了。

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int l,w,h;
     
    
   

    

     

    
    

     

      }box[111];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int dp[111];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool cmp(node a,node b)//长宽比较函数
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   if(a.l>b.l) return true;
     
    
   

    

     

    
    

     
   if(a.l==b.l&&a.w>b.w) return true;
     
    
   

    

     

    
    

     
   return false;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int d[3],n,i,j,c=1,k,sumh;
     
    
   

    

     

    
    

     
	while(scanf("%d",&n)!=EOF&&n)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

       k=0;
     
    
   

    

     

    
    

     
		for(i=0;i<n;i++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&d[0],&d[1],&d[2]); 
     
    
   

    

     

    
    

     

      			sort(d,d+3);
     
    
   

    

     

    
    

     
			//将数据转换成多种形式的长方体
     
    
   

    

     

    
    

     

      			box[k].l=d[2];box[k].w=d[1];box[k].h=d[0];k++;
     
    
   

    

     

    
    

     

      			box[k].l=d[2];box[k].w=d[0];box[k].h=d[1];k++;
     
    
   

    

     

    
    

     

      			box[k].l=d[1];box[k].w=d[0];box[k].h=d[2];k++;	 
     
    
   

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     

      		sort(box,box+k,cmp);//长宽排序
     
    
   

    

     

    
    

     
		for(i=0;i<k;i++) dp[i]=box[i].h;//初始化
     
    
   

    

     

    
    

     
		for(i=k-2;i>=0;i--)//跟一维的类似
     
    
   

    

     

    
    

     
			for(j=i+1;j<k;j++)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(box[i].l>box[j].l && box[i].w>box[j].w  && dp[i]<dp[j]+box[i].h)
     
    
   

    

     

    
    

     

       dp[i]=dp[j]+box[i].h;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      			sumh=dp[0];
     
    
   

    

     

    
    

     
			for(i=0;i<k;i++)
     
    
   

    

     

    
    

     
 if(sumh<dp[i]) sumh=dp[i];
     
    
   

    

     

    
    

     
			printf("Case %d: maximum height = %d\n",c++,sumh);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
   return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

POJ3616

链接：http://poj.org/problem?id=3616

题目大意：

在一个农场里，在长度为N个时间可以挤奶，但只能挤M次，且每挤一次就要休息t分钟；

其实不难，脑子要灵活，只要先对时间排序就好啦。

dp[i]表示i段最大值

  

   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <vector>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #include <limits.h>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int dp[10050];
     
    
   

    

     

    
    

     

      struct sa{
     
    
   

    

     

    
    

     
 int x,y,sum;
     
    
   

    

     

    
    

     

      }p[10050];
     
    
   

    

     

    
    

     

      int cmp(const sa a,const sa b){
     
    
   

    

     

    
    

     
 if(a.x==b.x)
     
    
   

    

     

    
    

     
 return a.y<b.y;
     
    
   

    

     

    
    

     
 return a.x<b.x;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 int n,m,t;
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&n,&m,&t);
     
    
   

    

     

    
    

     
 for(int i=0;i<m;i++){
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].sum);
     
    
   

    

     

    
    

     

       p[i].y+=t;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(p,p+m,cmp);//这一步很关键，时间是有顺序的
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for(int i=m-1;i>=0;i--){
     
    
   

    

     

    
    

     

       dp[i]=p[i].sum;
     
    
   

    

     

    
    

     
 for(int j=i+1;j<m;j++){
     
    
   

    

     

    
    

     
 if(p[j].x>=p[i].y)
     
    
   

    

     

    
    

     

       dp[i]=max(dp[i],dp[j]+p[i].sum);//转移方程
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int maxx=0;
     
    
   

    

     

    
    

     
 for(int i=0;i<m;i++)
     
    
   

    

     

    
    

     

       maxx=max(maxx,dp[i]);
     
    
   

    

     

    
    

     
 cout<<maxx<<endl;
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

poj1088

http://poj.org/problem?id=1088

当初做的时候死也想不出dp顺序，是脑子太死了，非想着按顺序推，其实按高低排了序就很好搞了。

两种思路：都是从小到大排序。可以以四周为条件更新自己，或者用自己做条件对别人更新。

dp(i,j)表示从点(i,j)出发的最长滑行长度。 

排序以后从小到大更新就保证了比它小的一定是正确的最长长度。

第一种思路：周围比它小的里面挑dp最大的，再加一就ok

第二种思路：把周围比它高的点都比较，需要更新就更新。举个例子：if  H(i+1,j) > H(i,j)  // H代表高度dp(i+1,j) = max(dp(i+1,j),dp(i,j)+1) 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81811310