随笔-141  评论-9  文章-3  trackbacks-0
题意:
Q1:LIS,最长长度为s
Q2:有多少个长度为s的子序列
Q3:若A[1]和A[n]可多次使用,问可以取多少个s长度的子序列

建模:

Q1:LIS,DP, F[i]表示以第i位为开头的最长上升序列的长度,求出最长上升序列长度K
for (int i=N;i>=1;i--){
    F[i] 
= 1;
    
for (int j=i+1;j<=N;j++)
        
if (A[j] > A[i] && F[j]+1 > F[i])
            F[i] 
= F[j]+1;
    
if (F[i] > Ans)
        Ans 
= F[i];
}

Q2:
1、把序列每位i拆成两个点<i.a>和<i.b>,从<i.a>到<i.b>连接一条容量为1的有向边。
2、建立附加源S和汇T,如果序列第i位有F[i]=K,从S到<i.a>连接一条容量为1的有向边。
3、如果F[i]=1,从<i.b>到T连接一条容量为1的有向边。
4、如果j>i且A[i] < A[j]且F[j]+1=F[i],从<i.b>到<j.a>连接一条容量为1的有向边。

求最大流,为第二问的解。

Q3:令(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大,再求一次网络最大流,就是第三问结果。
posted on 2011-03-10 11:10 小阮 阅读(614) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

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