【网络流24题-洛谷P2766 最长不下降子序列问题】

题目描述

«问题描述:

给定正整数序列x1,…,xn 。

(1)计算其最长不下降子序列的长度s。

(2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。

(3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。

«编程任务:

设计有效算法完成(1)(2)(3)提出的计算任务。

输入输出格式

输入格式:

第1 行有1个正整数n,表示给定序列的长度。接下来的1 行有n个正整数n:x1, …, xn。

输出格式:

第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。

输入输出样例

输入样例#1:

输出样例#1:

说明

\(n\le 500\)

第一问可直接用\(LIS\)的DP算法解决,具体不再详述,设\(F[i]\)代表以\(a_i\)结尾的最长的不下降子序列长度,注意,不下降是\(\le\)而不是\(<\)!

第二问与第三问可用网络流来解决,对于第二问,为了保证每个点只被选一次,很经典的做法就是拆点,把一个点拆成<i.A>与<i.B>两个点,并且之间连一条容量为1的边,这个1就是保证只选1次的。然后对于\(a_i\)与\(a_j\),若有\(j<i\)且\(F[j]+1==F[i]\),则在<j.B>与<i.A>之间连一条容量为1的边,最后,对于所有\(F[i]=1\)的点,用超级源点\(S\)与其对应的<i.A>相连,对于所有\(F[i]==maxL\)(maxL代表最长不下降子序列的最长长度)的点,用超级汇点\(T\)与其对应的<i.B>相连。跑一遍最大流,最大流就是长度为maxL的子序列个数。

至于第三问,由于\(x_1\)与\(x_n\)可以随便选,所以解除两点的限制就是了,也就是将< S,<1.A> >,< <1.A>,<1.B> >,

< <n.B>,T >,< <n.A>,<n.B> >四条边的容量赋值为inf(无穷大)即可,当然,对\(x_n\)这么处理的前提是\(x_n\)在长度为maxL的子序列中,也就是说\(F[n]==maxL\)才行。

代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*