acwing-2180. 最长递增子序列问题(最大流+拆点+最长上升子序列)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

给定正整数序列 x1,⋯,xn。

计算其最长递增子序列的长度 s。
计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。（给定序列中的每个元素最多只能被取出使用一次）
如果允许在取出的序列中多次使用 x1 和 xn，则从给定序列中最多可取出多少个长度为 s 的递增子序列。
注意:递增指非严格递增。

输入格式
第 1 行有 1 个正整数 n，表示给定序列的长度。

接下来的 1 行有 n 个正整数 x1,⋯,xn。

输出格式
第 1 行输出最长递增子序列的长度 s。

第 2 行输出可取出的长度为 s 的递增子序列个数。

第 3 行输出允许在取出的序列中多次使用 x1 和 xn 时可取出的长度为 s 的递增子序列个数。

数据范围
1≤n≤500

输入样例：
4
3 6 2 5
输出样例：
2
2
3

题解
当一个点只能被选一次的时候可以使用拆点的技术，同理可以选择k次的话，就从入点到出点连接一条流为K的边。注意源点对x1的影响

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 251010, INF = 1e8;
int n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int g[N], w[N];
void add(int a, int b, int c)
{ 

e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}
bool bfs()
{ 

int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{ 

int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{ 

int ver = e[i];
if (d[ver] == -1 && f[i])
{ 

d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
int find(int u, int limit)
{ 

if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{ 

cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{ 

int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{ 

int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main()
{ 

scanf("%d", &n);
S = 0, T = n * 2 + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
int s = 0;
for (int i = 1; i <= n; i ++ )
{ 

add(i, i + n, 1);
g[i] = 1;
for (int j = 1; j < i; j ++ )
if (w[j] <= w[i])
g[i] = max(g[i], g[j] + 1);
for (int j = 1; j < i; j ++ )
if (w[j] <= w[i] && g[j] + 1 == g[i])
add(n + j, i, 1);
s = max(s, g[i]);
if (g[i] == 1) add(S, i, 1);
}
for (int i = 1; i <= n; i ++ )
if (g[i] == s)
add(n + i, T, 1);
printf("%d\n", s);
if (s == 1) printf("%d\n%d\n", n, n);
else
{ 

int res = dinic();
printf("%d\n", res);
for (int i = 0; i < idx; i += 2)
{ 

int a = e[i ^ 1], b = e[i];
if (a == S && b == 1) f[i] = INF;
else if (a == 1 && b == n + 1) f[i] = INF;
else if (a == n && b == n + n) f[i] = INF;
else if (a == n + n && b == T) f[i] = INF;
}
printf("%d\n", res + dinic());
}
return 0;
}