题意：
求出最长上升子序列的长度k，并找出序列中最长上升子序列的个数。
思路：
先预处理LIS，然后拆点建图，对每一个LIS化为图中一条流量为1的边，用最大流来处理。
对每个点i拆为\(i\)和\(i+n\)，连边\((i,i+n,1)\)，设源点为0，汇点为\(2*n+1\)，然后根据求出的LIS，对每个\(d_i=1\)的点（LIS对应的边的起点），连边\((0,i,1)\)，若\(d_i=k\)(LIS对应的边的终点)，连边\((i+n,2*n+1,1)\)，对\(j>i\)，若\(d_j=d_i+1\)（即j所在的上升子序列可由i所在的构成），连边\((i+n,j,1)\)
现在来分析这样建图的原因，因为所有边的流量为1，所以每个点只会被访问一次，每一条边（即访问顺序为从求解LIS过程中\(d_i=1\)的点一直加1递增到k的点），便对应一个最长上升子序列，这样LIS为k的个数即为图的最大流。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);
const int INF = 0x3f3f3f3f;
const int MAXN = 10000;
const int MAXM = 1000000;
struct Edge
{
int to, next, cap, flow;
} edge[MAXM];
int tol;
int head[MAXN], id[MAXM];
int gap[MAXN], dep[MAXN], pre[MAXN], cur[MAXN];
void init()
{
tol = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w, int rw = 0)
{
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].next = head[u];
edge[tol].flow = 0;
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rw;
edge[tol].next = head[v];
edge[tol].flow = 0;
head[v] = tol++;
}
int ISAP(int start, int end, int N)
{
memset(gap, 0, sizeof(gap));
memset(dep, 0, sizeof(dep));
memcpy(cur, head, sizeof(head));
int u = start;
pre[u] = -1;
gap[0] = N;
int ans = 0;
while (dep[start] < N)
{
if (u == end)
{
int Min = INF;
for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to])
if (Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to])
{
edge[i].flow += Min;
edge[i ^ 1].flow -= Min;
}
u = start;
ans += Min;
continue;
}
bool flag = false;
int v;
for (int i = cur[u]; i != -1; i = edge[i].next)
{
v = edge[i].to;
if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u])
{
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if (flag)
{
u = v;
continue;
}
int Min = N;
for (int i = head[u]; i != -1; i = edge[i].next)
if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
{
Min = dep[edge[i].to];
cur[u] = i;
}
--gap[dep[u]];
if (!gap[dep[u]])
return ans;
dep[u] = Min + 1;
++gap[dep[u]];
if (u != start)
u = edge[pre[u] ^ 1].to;
}
return ans;
}
int s[MAXN], d[MAXN];
int LIS(int length)
{
int ans = 0;
for (int i = 1; i <= length; ++i)
{
d[i] = 1;
for (int j = 1; j < i; ++j)
{
if (s[j] < s[i] && d[j] >= d[i])
d[i] = d[j] + 1;
}
if (ans < d[i])
ans = d[i];
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
FILEREAD
#endif
FIO
int n;
while (cin >> n)
{
for (int i = 1; i <= n; ++i)
cin >> s[i];
int k = LIS(n);
init();
for (int i = 1; i <= n; ++i)
{
addedge(i, i + n, 1);
if (d[i] == 1)
addedge(0, i, 1);
if (d[i] == k)
addedge(i + n, (n << 1) + 1, 1);
for (int j = i + 1; j <= n; ++j)
if (d[j] == d[i] + 1)
addedge(i + n, j, 1);
}
cout << k << endl;
cout << ISAP(0, (n << 1) + 1, (n + 1) << 1) << endl;
}
return 0;
}