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 阅读(131) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2024年4月

日

一

二

三

四

五

六

常用链接

留言簿(8)

随笔档案

文章档案

2009年3月 (1)

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

最新评论

阅读排行榜

评论排行榜