posts - 43,  comments - 9,  trackbacks - 0
250p CubeStickers
给出若干个方形木板,每个木板有一种颜色。现在要选出其中6个,围出一个立方体。问是否可能使转出的立方体,任意两个相邻的面颜色不同。
直接按木板的总数分情况讨论就可以,但是我漏想了一种情况@.@
其实显然,同一种颜色最多能用两次,所以统计每种木板能用的个数之和,sigma(min(count[i],2)),和不小于6则可行。

500p CubePacking
给出Ns个边长为1的立方体和Nb个边长为L(2<=L<=10)的立方体。要找一个体积最小的长方体,使得可以把所有立方体堆进去。保证结果不超int32。
正是因为不超int32,所以可以直接枚举两条棱x,y,算第3条z的最小值。枚举时循环条件 x*x*x <= INF, x*y*y <= INF。计算z的最小值时要注意除法要向上取整,而且判断能否把边长为L的立方体都放进去的条件是(x/L)*(y/L)*(z/L) >= Nb,如果z小了,要加到足够大为止。
[枚举]

900p CubeBuilding
大小相同的红、绿、蓝色的立方体,分别给R、G、B个(R,G,B<=25)。把这些立方体全部搭积木一样的堆到N*N(N<=25)的格子棋盘中。可以在任意格子中堆任意高的立方体。规定一种方案是合法的,如果从北向南看的侧视图中只有一种颜色。问一共有多少种堆砌的方案。
可以先考虑N*1的棋盘,也就是侧视图中棋盘宽度是1。先考虑没有颜色的方块怎么放,再去染色。这样不管怎么堆,看到的方块数总是等于所有格子堆的最大高度,则需要固定颜色的方块数就为这个高度,剩下的方块可以任意染色。同理N*N的棋盘,需要固定颜色的方块数等于所有列中需要固定的数量之和。要求的答案就是,先枚举固定方块的数目,把它们染某一种颜色,剩下的方块可以用组合数直接算出有多少种染色方案,乘起来,最后求和。
关键就是要求出每一种固定方块数目的前提下,不考虑颜色,有多少种堆放方法。
由前面的讨论知道,可以先在N*1的棋盘上按行扩展,需要记录的状态是当前已使用的方块数,当前的最大高度。
然后利用这个结果按列扩展,记录的状态是当前已使用的方块数,当前已固定的方块数。
ps.染色之前的方案数只用求一次,之后分别把固定的方块染成3种不同颜色,只要用组合数分别算3次,加起来就行了。
O(9*N^5)的算法,时限有点紧。
[DP]
posted on 2011-06-01 00:04 wolf5x 阅读(222) 评论(0)  编辑 收藏 引用 所属分类: topcoder

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜