考虑模拟整个算法的过程来确定转移的方向

懵逼的 题目

传送至 Luogu

扯淡的 题解

%%%Refun太强辣

LIS长度直接$n^2$DP…
求序列个数…直接把每一个点和他在序列中可能的后继连边, 然后跑最大流…
具体连边是根据DP中的f[]来连的…

  1. 每个点拆成两个, 连边, 容量为1, 代表一个节点只能选一次
  2. 节点A向B’连边, 容量为1, 当且仅当在原序列中f[A] + 1 = f[B] && a[A] < a[b] && A < B…即在LIS中A是B的一个可行的前驱(我就是忘了最后一个条件WA了好久)…
  3. A’向T连边, 当且仅当f[A] = maxf, 即以A为结尾的最长不下降子序列就是最长的那个…这也就保证了找到的序列都是可行的序列(就是没有看到这点我才写了个奇奇怪怪的错的费用流)…%%%REfun太强啦

第三问就是直接把1和n拆出的两点之间的边改流量为INF…然后在原图上继续跑最大流就行…

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXU (500 + 5)
#define MAXN (10000 + 5)
#define MAXM (50000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) (((a - 1) ^ 1) + 1)
#define INF (0x7ffffff)
#define bh(a) (((a) < MAXU) ? ((a) + MAXU) : (a))
#define ubh(a) (((a) > (MAXU) ? ((a) - MAXU)) : (a))
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
    int cap;
    int flow;
    edg() {}
    edg(int a, int b, int c, int d, int e): from(a), to(b), next(c), cap(d), flow(e) {}
}b[MAXM << 1];
int cntb = 0;
int g[MAXN];

int n;
int a[MAXU];
int bq[MAXU];

int dis[MAXN];

int dplength;
int f[MAXU];

int ans2;
int ans3;

void adn(int, int, int);
void init();
bool bfs();
int dinic(int, int);
void solve();

void rep();
void dp();
bool cmp(int, int);
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        bq[i] = a[i];
    }
    rep();
    dp();
    init();
    solve();
    printf("%d\n%d\n%d", dplength, ans2, ans3);
    return 0;
}
void rep()
{
    sort(bq + 1, bq + n + 1, cmp);
    bool vis[MAXU];
    memset(vis, false, sizeof(vis));
    int bn = unique(bq + 1, bq + n + 1) - bq - 1;
    for (int i = 1; i <= bn; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[j] == bq[i] && (!vis[j]))
            {
                vis[j] = true;
                a[j] = i;
            }
        }
    }
}
void dp()
{
    for (int i =  1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (a[i] >= a[j])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        dplength = max(f[i], dplength);
    }
    if (dplength == 1)
    {
        printf("%d\n%d\n%d\n", 1, n, n);
        exit(0);
    }
}
void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap, 0);
    g[from] = cntb;
}
void init()
{
    for (int i = 1; i <= n; i++)
    {
        adn(i, bh(i), 1);
        adn(bh(i), i, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == dplength)
        {
            adn(bh(i), t, INF);
            adn(t, bh(i), INF);
        }
        else 
        {
            if (f[i] == 1)
            {
                adn(s, i, INF);
                adn(i, s, INF);
            }
            for (int j = i + 1; j <= n; j++)
            {
                if (f[j] == f[i] + 1 && a[j] >= a[i])
                {
                    adn(bh(i), j, 1);
                    adn(j, bh(i), 0);
                }
            }
        }
    }
}
bool bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (!dis[b[i].to] && b[i].cap > b[i].flow)
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
int dinic(int dq, int maxf)
{
    if (dq == t || maxf == 0)
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (dis[b[i].to] == dis[dq] + 1 && b[i].cap > b[i].flow)
        {
            int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            maxf -= zl;
            re += zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }
    }
    return re;
}
void solve()
{
    while (bfs())
    {
        ans2 += dinic(s, INF);
    }
    ans3 = ans2;

    adn(1, bh(1), INF);
    adn(bh(1), 1, 0);

    adn(n, bh(n), INF);
    adn(bh(n), n, 0);

    while (bfs())
    {
        ans3 += dinic(s, INF);
    }
}
bool cmp(int x, int y)
{
    return x < y;
}

/*
4
3 6 2 5
*/

By 全不见有伶俐起来的希望 的 Cansult