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
閱讀(146)
評論(0)
編輯
收藏
引用
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Copyright ©2025 KNIGHT Powered By:
博客園
模板提供:
滬江博客
<
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入門手冊(6484)
2.?淺談2—SAT問題(6233)
3.?分而治之算法---距離最近的點對 (2784)
4.?poj 3648 Wedding(1447)
5.?最小樹形圖(1315)
評論排行榜
1.?Making the Grade(3)
2.?poj 3648 Wedding(3)
3.?[ZZ]后綴數組(2)
4.?最優比例生成樹(2)
5.?這是個問題!!!(2)
国产亚州精品女人久久久久久
|
亚洲AV成人无码久久精品老人
|
午夜精品久久久久久久无码
|
亚洲午夜福利精品久久
|
久久精品中文无码资源站
|
激情久久久久久久久久
|
少妇人妻综合久久中文字幕
|
久久精品草草草
|
亚洲级αV无码毛片久久精品
|
久久精品国产91久久综合麻豆自制
|
久久久久亚洲AV无码去区首
|
久久精品成人免费网站
|
亚洲国产精品无码久久久久久曰
|
亚洲国产精品18久久久久久
|
久久天天躁狠狠躁夜夜2020
|
久久久久人妻一区精品色
|
色综合久久久久综合99
|
久久久青草久久久青草
|
香蕉久久av一区二区三区
|
久久人人爽人人爽人人片AV麻豆
|
亚洲国产成人久久一区WWW
|
国内精品久久久久久99蜜桃
|
亚洲人成无码www久久久
|
久久成人18免费网站
|
国产精品久久久久jk制服
|
亚洲国产精品久久电影欧美
|
久久人与动人物a级毛片
|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
亚洲AV无码成人网站久久精品大
|
人人狠狠综合久久亚洲
|
久久国产成人精品麻豆
|
91久久婷婷国产综合精品青草
|
伊人久久综合无码成人网
|
久久综合伊人77777
|
久久亚洲天堂
|
欧美粉嫩小泬久久久久久久
|
久久久久亚洲爆乳少妇无
|
狠狠色丁香久久婷婷综合
|
久久天天躁狠狠躁夜夜躁2014
|
久久这里只精品国产99热
|
精品国产乱码久久久久久1区2区
|