题意:给定一个序列,求最长上升子序长度以及有多少组,每个元素只能用一次。
思路:先求LIS,记为num,求出以每个点为末尾的最长子序列长度。窝们将每个点点拆成i和i',i --> i' 容量为1,源点连接d[ i ]=1的点,容
量为1,汇点连接d[ i ]=num的点,容量为1。对于j<i, a[ j ] < a[ i ],d[ i ] = d[ j ] + 1的情况,j' --> i 连一条容量为1的边,跑最大流即可。详见代码:
/*********************************************************
file name: hdu3998.cpp
author : kereo
create time: 2015年02月17日 星......
阅读全文