The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest To Miss Our Children Time

2024-01-10 08:18

本文主要是介绍The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest To Miss Our Children Time,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=4001

Problem Description
Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game will brings us lots of happy time! LLL is a nostalgic boy, now he grows up. In the dead of night, he often misses something, including a simple game which brings him much happy when he was child. Here are the game rules: There lies many blocks on the ground, little LLL wants build "Skyscraper" using these blocks. There are three kinds of blocks signed by an integer d. We describe each block's shape is Cuboid using four integers ai, bi, ci, di. ai, bi are two edges of the block one of them is length the other is width. ci is
thickness of the block. We know that the ci must be vertical with earth ground. di describe the kind of the block. When di = 0 the block's length and width must be more or equal to the block's length and width which lies under the block. When di = 1 the block's length and width must be more or equal to the block's length which lies under the block and width and the block's area must be more than the block's area which lies under the block. When di = 2 the block length and width must be more than the block's length and width which lies under the block. Here are some blocks. Can you know what's the highest "Skyscraper" can be build using these blocks?


Input
The input has many test cases.
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks.
From the second to the n+1'th lines , each line describing the i‐1'th block's a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2).
The input end with n = 0.


Output
Output a line contains a integer describing the highest "Skyscraper"'s height using the n blocks.


Sample Input
3
10 10 12 0
10 10 12 1
10 10 11 2
2
10 10 11 1
10 10 11 1
0


Sample Output
24
11
思路:这一题属于dp题,难点我认为就是排序的问题,总是把条件苛刻的放在最下面。。。。。

代码:

#include<iostream>
#include<algorithm>
using namespace std;
struct block{ long long  a,b,c,d;}aa[1005];
bool cmp(block x,block y)
{ if(x.a!=y.a) return x.a<y.a;//按长从小到大排序。if(x.b!=y.b) return x.b<y.b;//按宽从小到大排序。return x.d>y.d;//按编号从大到小排序
}
long long dp[1005];
int main()
{ int n;while(cin>>n,n){  for(int i=0;i<n;i++){ cin>>aa[i].a>>aa[i].b>>aa[i].c>>aa[i].d;if(aa[i].a<aa[i].b) swap(aa[i].a,aa[i].b);dp[i]=0;}    sort(aa,aa+n,cmp);long long  ans=0;for(int i=0;i<n;++i){  dp[i]=aa[i].c;for(int j=0;j<i;++j)//每次都把当前的block和它前面的比较从而确定把该block放在最上面时的最大厚度。{ if(aa[i].d==0&&aa[i].a>=aa[j].a&&aa[i].b>=aa[j].b)dp[i]=max(dp[i],dp[j]+aa[i].c);if(aa[i].d==1&&aa[i].a>=aa[j].a&&aa[i].b>=aa[j].b&&(aa[i].a>aa[j].a||aa[i].b>aa[j].b))dp[i]=max(dp[i],dp[j]+aa[i].c);if(aa[i].d==2&&aa[i].a>aa[j].a&&aa[i].b>aa[j].b)dp[i]=max(dp[i],dp[j]+aa[i].c);}if(dp[i]>ans) ans=dp[i];//把每次求出的最大厚度和最大厚度相比从而求出最大厚度。}cout<<ans<<endl;
}return 0;}


这篇关于The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest To Miss Our Children Time的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/590145

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

Regionals 2004 Asia - Beijing Argus 小根堆

点击打开链接 小根堆 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokeni

linux 下Time_wait过多问题解决

转自:http://blog.csdn.net/jaylong35/article/details/6605077 问题起因: 自己开发了一个服务器和客户端,通过短连接的方式来进行通讯,由于过于频繁的创建连接,导致系统连接数量被占用,不能及时释放。看了一下18888,当时吓到了。 现象: 1、外部机器不能正常连接SSH 2、内向外不能够正常的ping通过,域名也不能正常解析。

python内置模块datetime.time类详细介绍

​​​​​​​Python的datetime模块是一个强大的日期和时间处理库,它提供了多个类来处理日期和时间。主要包括几个功能类datetime.date、datetime.time、datetime.datetime、datetime.timedelta,datetime.timezone等。 ----------动动小手,非常感谢各位的点赞收藏和关注。----------- 使用datet

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追