dp打开思路3:HDU1069 POJ3616 POJ1088

举报
兔老大 发表于 2021/04/26 01:02:37 2021/04/26
【摘要】 HDU 1069 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1069 题意:把给定的长方体(不限)叠加在一起,叠加的条件是,上面一个长方体的长和宽都比下面长方体的长 和宽短;求这些长方体能叠加的最高的高度.(其中(3,2,1)可以摆放成(3,1,2)、(2,1,3)等). 思路:其实就是求最长的单调递减序列。在长和宽...

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。