大致题意:
给你n种箱子,每种箱子都有各自的长宽高,每种箱子都有无限多个。如果一个箱子的长和宽都小于另一个箱子,那么这个箱子就可以放在那个箱子上面。求这n种箱子最多可以堆多高。
大致思路:
首先排序,按照长和宽中最长的那个。保证如果如果箱子i可以放在箱子j上面的话则j<i。然后就是简单的DP~~
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
const int nMax=1000;
class node{
public:
int big,sma,h;
}block[nMax];
bool cmp(node a,node b){
if(a.sma<b.sma)return 0;
if(a.sma==b.sma){
if(a.big<=b.big)return 0;
return 1;
}
return 1;
}
int dp[nMax];
int main(){
int n,i,j,a,b,c,m,ans,cas=1;
while(scanf("%d",&m)&&m){
n=0;
ans=0;
while(m--){
scanf("%d%d%d",&a,&b,&c);
block[n].big=max(a,b);
block[n].sma=min(a,b);
block[n++].h=c;
block[n].big=max(a,c);
block[n].sma=min(a,c);
block[n++].h=b;
block[n].big=max(b,c);
block[n].sma=min(b,c);
block[n++].h=a;
}
sort(block,block+n,cmp); //大->小
for(i=0;i<n;i++){
dp[i]=block[i].h;
}
for(i=0;i<n;i++){
for(j=0;j<i;j++){
if(block[j].big>block[i].big&&block[j].sma>block[i].sma){
dp[i]=max(dp[i],dp[j]+block[i].h);
ans=max(dp[i],ans);
}
}
}
printf("Case %d: maximum height = %d\n",cas++,ans);
}
return 0;
}
分享到:
相关推荐
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
HDOJ题目分类HDOJ题目分类HDOJ题目分类
Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 Author HDOJ 代码: #include int main() { ...
hdoj 2013 多校训练3标程+解题报告
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
hdoj解题代码,题目为1000-1050
codj,hdoj的源码(50-60题)
hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码