Knight
KNIGHT
C++博客
首页
新随笔
联系
聚合
管理
posts - 74, comments - 33, trackbacks - 0
今天下午的做的工大的WarmUp
9道题(到现在做出来的有5道题)
HIT WarmUp
其中3道题目是二分图,2道题目是DP(大概都采用了位运算)可能是工大的领队有意为之吧。
A。
因为有条件
You should assume that the gumdrop radii are sufficiently large that no three gumdrops can be simultaneously in contact with each other while fitting in the tube.
而且糖总数少于16,就可以想到最多DP[1<<16][16],而且记录每个点的圆心高度,可以计算两个圆之间的高度差为 sqrt((d-(ra+rb))*(d-(ra+rb))-(ra+rb)*(ra+rb));DP[i][j]表示已经有i(2进制表示的为1的个数),j表示最高位为第j个球,则可以递推:
for
(i
=
1
;i
<
all;i
++
)
for
(j
=
0
;j
<
n;j
++
)
if
(dp[i][j]
>
1e
-
8
)
{
for
(k
=
0
;k
<
n;k
++
)
if
(
!
((
1
<<
k)
&
i))
{
double
temp
=
DIS(k,j);
if
(dp[(
1
<<
k)
|
i][k]
<
1e
-
8
||
(dp[(
1
<<
k)
|
i][k]
-
dp[i][j]
+
temp
>
1e
-
8
))
dp[(
1
<<
k)
|
i][k]
=
dp[i][j]
+
temp;
}
}
随后枚举dp[all=(1<<n)-1][j]中的最小值即可。
B。
属于二分图中的最小点覆盖,在二分图中存在最小路径覆盖=点数-最大匹配数(建议自己看下证明,这里我就不证明了)
D。
以前做过,忘记了是最大匹配还是什么,总之最大匹配模板搞定。
E。
同A题类似,DP过程一样,只是最优状态有所不同,建议先做E,在做A。(完全属于一个类型的DP)
G。
二分图中存在最小点覆盖=最大匹配数
H。
很郁闷的一道题目,一直TLE,郁闷,等待大牛的解题报告。如何才能实现不超时的算法?
I。
根本没看。。。。。。
posted on 2009-05-17 21:20
KNIGHT
阅读(135)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2009年5月
>
日
一
二
三
四
五
六
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年6月 (4)
2009年5月 (14)
2009年4月 (12)
2009年3月 (10)
2009年2月 (12)
2009年1月 (10)
2008年12月 (12)
文章档案
2009年3月 (1)
Friends
OJ
HEU
PKU
ZJU
搜索
最新评论
1. re: (转载)TopCoder入门手册
好,学习了
--wuyiqi
2. re: Knights
评论内容较长,点击标题查看
--Lightning
3. re: Knights
请问您说的奇偶性不同的x,y是指什么?
--Lightning
4. re: [ZZ]后缀数组[未登录]
@爱上对方
请你仔细阅读标题
【ZZ】转载。。懂
--Knight
5. re: [ZZ]后缀数组
请你不要抄
--爱上对方
阅读排行榜
1. (转载)TopCoder入门手册(6458)
2. 浅谈2—SAT问题(6167)
3. 分而治之算法---距离最近的点对 (2727)
4. poj 3648 Wedding(1431)
5. 最小树形图(1300)
评论排行榜
1. Making the Grade(3)
2. poj 3648 Wedding(3)
3. [ZZ]后缀数组(2)
4. Knights(2)
5. 感(2)