HDOJ 1069 DP
2024-10-13 06:59:42
开启DP之路
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1069
描述一下:
就是给定N(N<=20)个方体,让你放置,求放置的最高高度,限制条件是:上面的物体的长度和宽度都小于下面物体。
觉得这道题目很经典:
于是贴下
。我们可以把一个方体看成六个,想到这里,然后求最高,方程很简单了 ,
if (a[j].x>a[i].x&&a[j].y>a[i].y)
ans=max(ans,a[j].h+a[i].h);
a[i].h=ans;#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int x,y,h;
}a[];
int cmp(node x,node y)
{
if (x.x==y.x) return x.y>y.y;
return x.x>y.x;
}
int main()
{
int n;
int t=;
while (scanf("%d",&n)!=EOF)
{
t++;
if (n==) break;
int xx,yy,zz,nn=;
for (int i=;i<=n;i++)
{
scanf("%d%d%d",&xx,&yy,&zz);
a[++nn].x=xx;a[nn].y=yy;a[nn].h=zz;
a[++nn].x=xx;a[nn].y=zz;a[nn].h=yy;
a[++nn].x=yy;a[nn].y=xx;a[nn].h=zz;
a[++nn].x=yy;a[nn].y=zz;a[nn].h=xx;
a[++nn].x=zz;a[nn].y=yy;a[nn].h=xx;
a[++nn].x=zz;a[nn].y=xx;a[nn].h=yy;
}
sort(a+,a+nn+,cmp);
a[].h=;
a[].x=a[].y=; for (int i=;i<=nn;i++)
{
int ans=;
for (int j=;j<i;j++)
if (a[j].x>a[i].x&&a[j].y>a[i].y)
ans=max(ans,a[j].h+a[i].h);
a[i].h=ans;
}
int ans=;
for (int i=;i<=nn;i++)
ans=max(ans,a[i].h);
printf("Case %d: maximum height = %d\n",t,ans);
}
return ;
}
求出A[1].H--A[N].H的最大ok了
最新文章
- Socket聊天程序——客户端
- MATLAB连接ACCESS数据库
- Ajax --- 数据请求
- IE9 不F12打开控制台,代码不执行。打开后正常
- LPC43xx SGPIO DMA and Interrupts
- 15套精美的免费界面设计 PSD 素材【免费下载】
- 解决eclipse-helios中Errors running builder JavaScript Validator的问题
- Android中常见的MVC模式
- Windows下移动硬盘无法识别但是Mac下可以识别
- jQuery使用serialize(),serializeArray()方法取得表单数据+字符串和对象类型两种表单提交的方法
- python---进程与线程
- asp.net core系列 60 Ocelot 构建服务认证示例
- JAVA自学笔记20
- 基于R语言的ARIMA模型
- Reinforcement Learning 的那点事——强化学习(一)
- JDBC(3)—ResultSet结果集
- cnblogs插件jiathis
- init进程接管孤儿进程的验证
- 分布式下的session处理方式
- 不得不知的npm常用指令