这题第二问只会写网络流怎么破???

第二问一看就是最小路径覆盖,然后就写了网络流,实在不会DP写法啊啊!~!!求指教!

4 条评论

  • @ 2015-07-26 11:31:44

    假设最优情况下用了m套系统,且第i套系统中任意一发导弹一定大于第j套系统中任意一发(1<=j<i<=m)(如果不大于,那这一发完全可以扔到第j套系统去,有可能产生更优解),那么最长上升子序列一定只会取每套系统中的某一发(每套系统内部导弹按拦截顺序一定坐标严格递减高度不上升,取了一发就不可能取另一发),长度为m。
    ps:YuChu苣蒻膜拜云神

  • @ 2014-08-17 10:20:57

    网络流大神orz

  • @ 2013-10-12 07:56:06

    会写网络流的大神来卖萌了。如果有升序的,那么肯定要再来一发。所以最长严格上升子序列。

  • @ 2013-10-12 00:34:40

    把上一问倒着求就ok了

  • 1

信息

ID
1303
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
7584
已通过
2014
通过率
27%
被复制
11
上传者