最长不下降子序列问题

题目描述

«问题描述:

给定正整数序列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: 复制

说明

n500


第一问用dp求出LIS长len和f[i]

把一个点拆成x, y

从s到f[i]=len的点x,流量为1

从f[i]=1的点y到t,流量为1

从点x到点y,流量为1

从a[j]≤a[i]且f[j]+1=f[i]的点iy到点jx,流量为1

第三问只需要接触1和n的流量限制就行了

注意:不下降时小于等于


 

发表评论