摘要: 动态规划总结 by Amber

  阅读全文
posted @ 2007-09-29 20:25 Felicia 阅读(3948) | 评论 (0)编辑 收藏
 
     摘要: 问题是求平面欧几里德最小生成树的第n - k小边。
平面欧几里德最小生成树是经典问题,可以做到O(nlogn)。具体做法是先对平面点进行三角剖分,时间复杂度是O(nlogn),三角剖分的边就是可能的在最小生成树的边。因为是平面图,所以有O(n)条边,在其上应用 Kruscal 算法即可。

  阅读全文
posted @ 2007-09-28 20:17 Felicia 阅读(777) | 评论 (0)编辑 收藏
 
     摘要: 漫谈扭结

  阅读全文
posted @ 2007-09-27 17:26 Felicia 阅读(1800) | 评论 (2)编辑 收藏
 
     摘要: 此问题可转化为求三角形垂心。我的做法是设垂心坐标为(x, y),然后利用垂直关系解方程。

  阅读全文
posted @ 2007-09-27 17:18 Felicia 阅读(652) | 评论 (1)编辑 收藏
 
     摘要: Ubuntu 6.10 @ Dell XPS M1210 安装手记

  阅读全文
posted @ 2007-09-27 15:21 Felicia 阅读(666) | 评论 (0)编辑 收藏
 
     摘要: 一首小诗……

  阅读全文
posted @ 2007-09-27 15:06 Felicia 阅读(192) | 评论 (0)编辑 收藏
 
     摘要: 平面点的曼哈顿最小生成树

  阅读全文
posted @ 2007-09-27 14:48 Felicia 阅读(1261) | 评论 (0)编辑 收藏
 
     摘要: 简单计算几何,我的做法是列出所有可能的切法(一共18种),求最优值。

  阅读全文
posted @ 2007-09-26 20:46 Felicia 阅读(572) | 评论 (1)编辑 收藏
 
     摘要: 构造所有的线段,然后枚举每对水平-竖直线段,求交点,然后计算四边形面积,求最大值。

  阅读全文
posted @ 2007-09-25 21:59 Felicia 阅读(621) | 评论 (0)编辑 收藏
 
     摘要: 强烈推荐此题!
状态压缩DP的好题!
分析见内

  阅读全文
posted @ 2007-09-24 21:12 Felicia 阅读(1142) | 评论 (4)编辑 收藏
仅列出标题
共15页: First 3 4 5 6 7 8 9 10 11 Last