首页 > 其他 > 详细

CF650D Zip-line

时间：2020-04-08 15:09:09      阅读：52      评论：0      收藏：0      [点我收藏+]

URL

https://codeforces.com/contest/650/problem/D

解法

考虑修改每个位置 \(i\) 后序列的 LIS，对两种情况取较大值：

  • LIS 经过 \(i\)，可以直接计算
  • LIS 不经过 \(i\)，就是要求原序列忽略 \(i\) 的 LIS。考虑原序列中经过每个位置的所有 LIS（最长的），这个位置在对应的所有 LIS 里的的下标是确定的。计 \(f(i)=k\) 为 \(i\) 在经过它的 LIS 里的下标，如果只有一个 \(f(i)=k\)，说明所有的最长 LIS 都经过它，因此不经过 \(i\) 的 LIS 应该减一。

实现

https://ideone.com/iHuO3i

CF650D Zip-line

原文：https://www.cnblogs.com/iefnah06/p/12659628.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！