题意:求最长上升子序列的长度和数量。
分析:用dp求出最长上升子序列m,dp数组存的就是该元素为子序列结尾的长度,源点与长度为1的点建边,长度为m的与汇点连边,然后枚举任意两个元素,ai,aj(ai>aj&&i>j&&dp[i]==dp[j]+1),j跟i连边,因为每个点只能选一次,所以边的容量都为1,求出最大流。
#include<stdio.h>
#include<string.h>
const int N=500;
const int inf=0x3fffffff;
int dis[N],gap[N],start,end,ans,dp[N],head[N],num;
struct edge
{
int st,ed,flow,next;
}e[N*5];
void ad......
阅读全文