posts - 74, comments - 33, trackbacks - 0

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 閱讀(152) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2009年5月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜