dp打开思路3：HDU1069 POJ3616 POJ1088

Bertha 。 2022-05-16 08:58 195阅读 0赞

HDU 1069

**题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=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][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][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)

[http_acm.hdu.edu.cn_showproblem.php_pid_1069]: http://acm.hdu.edu.cn/showproblem.php?pid=1069
[http_poj.org_problem_id_3616]: http://poj.org/problem?id=3616
[http_poj.org_problem_id_1088]: http://poj.org/problem?id=1088