poj1088滑雪
题意：找出矩阵中的最长下降序列的长度。
解题思路：
1.回溯，时间复杂度，指数级别。这是一种很容易想到的做法，不过会超时。
2.动态规划，时间复杂度O(N^2)。相信我们都学过一维的最长上升子序列问题，这一题是一维的变形，我们只需稍加转换就可以转换为一维的。
先来回想一下一维的最长上升子序列的做法：对一个给定的节点p，我们只需枚举p前面的所有节点的最长上升子序列的长度，用p前面的节点的长度去试图更新p的长度即可。
我们如何将本题转化为一维的问题呢？我们只需将矩阵中的所有点按照他的high排序，然后按照一维的处理即可。只不过p前面的节点在更新p时还要考虑他们在矩阵中的相对位置，因为只有跟p相邻的四个点才有可能去更新p点的长度。
代码

posted on 2013-04-16 18:36 小鼠标 阅读(397) 评论(0)  编辑 收藏 引用 所属分类: Java基础练习

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


<2012年8月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的，所以在OJ有时候“卡住”了也不要太灰心，没准真的不是自己的原因呢。
    加油，祝你好运啦！
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说，Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: （转）ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。？
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主，谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况，书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜