单链DNA

换了个地址:http://www.cnblogs.com/vizhen/

 

7月份HDOJ A题小结

7月份主要针对于以下几个类型:搜索,DP,图论(部分)。

搜索:主要是DFS和BFS,特别一点是注意剪枝。
   1010 Tempter of the Bone  DFS+奇偶剪枝。
             1016   Prime Ring Problem  简单的DFS,第一次没看清题目,没注意尾部和首部相加也要是素数。可以先用一个数组把素数先标记好,那DFS就很简单了。
              1181   变形课 简单的DFS。用邻接矩阵将首尾字母保存,从字母‘b’开始DFS搜索。注意跳过已经搜过的字母。
              1195   Open the Lock   2717 Catch That Cow  简单BFS。注意跳过已经搜索过的。
              1240   Aseroids!  简单的BFS。错了几次是因为没把数据用多维数组保存好。
              1241    Oil Deposits   DFS和BFS都可以。斜线方向也是可以的。
              1242   Rescue    BFS。但是注意可能由多个Freind,所以从Angle开始搜。
              1312   Red and Black  简单DFS。
              1198    Farm Irrigation 可以用BFS,但我是用“并查集”做的。

DP:这个是弱点,所以没做多少,只做一些简单的。
              1003  MaxSum 最长连续子序列,经典DP,基本DP。
              1024  MaxSum Plus Plus 关键是如何降维,将O^3最后变成O^2的,否则会超时。
              1114   Piggy-Bank 完全背包问题。
              1159   Common Subsequence  最长公共字串,经典DP问题。
              1203   I NEED A OFFER!0-1背包问题。
              1257   最少拦截系统  一个简单方法,利用vector 开一个动态数组,每次读一个数据,从前扫描过来,遇到比所读数据大的,就更新那个数据为所读数据,最后,该数组长度就是导弹系统个数。
              1559   最大子矩阵   对数组中的数据做下修改,对于a[i][j] 重新更新为 a[1][1]—a[i][j] 子矩阵的和,然后就可以搜一下整个数组就能得到最大子矩阵了。
              1428  漫步校园 先是从终点BFS到起点,把耗费保存在一个表中,然后再从起点DFS终点求的所有路线,但注意要记录已经遍历过的点,下次遍历就直接加上上次遍历所得的路线数目,否则会超时。

图论:主要做了 单源最短路径--Dijkstra算法,所有点的-Floyd算法;最小生成树--Prim算法,另外那个还没写过( = =! ); 最大子团--回溯法
              1217   Arbitrage  建立一个有向图,利用Floyd算法,问题也就是求通过其他点到自己有没有增加。
              1596  find the safest road 所有点最短路径--Floyd可以解决。
              1530  Maxumum Clique 最大子团  回溯法,就是耗时比较多。
              1162  Eddy’s picture  最小生成树--Prim算法
              1232 畅通工程 赤裸裸的并查集。
              1301 Jungle Roads 还是最小生成树

posted on 2010-08-07 23:06 Geek.tan 阅读(376) 评论(0)  编辑 收藏 引用 所属分类: ACM解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

公告

coding是我的寂寞,我是谁的寂寞

随笔分类(40)

随笔档案(48)

搜索

积分与排名

最新评论

评论排行榜