posts - 74, comments - 33, trackbacks - 0

9道題（到現(xiàn)在做出來(lái)的有5道題）HIT WarmUp
其中3道題目是二分圖，2道題目是DP（大概都采用了位運(yùn)算）可能是工大的領(lǐng)隊(duì)有意為之吧。
A。
因?yàn)橛袟l件? 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. 而且糖總數(shù)少于16，就可以想到最多DP[1<<16][16]，而且記錄每個(gè)點(diǎn)的圓心高度，可以計(jì)算兩個(gè)圓之間的高度差為 sqrt((d-(ra+rb))*(d-(ra+rb))-(ra+rb)*(ra+rb));DP[i][j]表示已經(jīng)有i(2進(jìn)制表示的為1的個(gè)數(shù))，j表示最高位為第j個(gè)球，則可以遞推：

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。
屬于二分圖中的最小點(diǎn)覆蓋，在二分圖中存在最小路徑覆蓋=點(diǎn)數(shù)-最大匹配數(shù)（建議自己看下證明，這里我就不證明了）
D。
以前做過(guò)，忘記了是最大匹配還是什么，總之最大匹配模板搞定。
E。
同A題類似，DP過(guò)程一樣，只是最優(yōu)狀態(tài)有所不同，建議先做E，在做A。（完全屬于一個(gè)類型的DP）
G。
二分圖中存在最小點(diǎn)覆蓋=最大匹配數(shù)
H。
很郁悶的一道題目，一直TLE，郁悶，等待大牛的解題報(bào)告。如何才能實(shí)現(xiàn)不超時(shí)的算法？
I。
根本沒(méi)看。。。。。。

posted on 2009-05-17 21:20 KNIGHT 閱讀(157) 評(píng)論(0) 編輯收藏引用