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

全栈程序员站长

发布于 2022-09-22 11:28:51

3810

大家好，又见面了，我是你们的朋友全栈君。

给定正整数序列 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;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168571.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java