给定正整数序列 x1∼xn x_1 \sim x_n ，以下递增子序列均为非严格递增。

  1. 计算其最长递增子序列的长度 s s 。
  2. 计算从给定的序列中最多可取出多少个长度为 s s 的递增子序列。
  3. 如果允许在取出的序列中多次使用 x1 x_1 和 xn x_n ，则从给定序列中最多可取出多少个长度为 s s 的递增子序列。

题解

题意不清的辣鸡题。。这里感谢 Menci 同学在博客里和 OJ 上都强调了 非严格递增 题意要求求出 “最长递增子序列” ，然而实际数据却是 “最长不下降子序列” 第一问直接 dp 即可，第二问第三问网络流解决。

第二问: 记第一问答案为 K K 。 首先在 dp 中，f(i) f(i) 表示以第 i 个元素结尾的最长不下降子序列长度， 然后我们将每个 (f(i)=1) (f(i) = 1) 与 源点连边，容量为 1 1 ， 每个 (f(i)=K) (f(i) = K) 向汇点连边，每个可能的转移连边，对于可能的转移 f(j)→f(i) f(j) \rightarrow f(i) ，需要满足的条件是 j<i j < i ，aj<ai a_j < a_i 且 f(j)+1=f(i) f(j) + 1 = f(i) 。

但是第二问要求的方案数其实是不允许在不同方案中选取相同元素的， 所以我们把每个点拆点限制容量。

第三问: 第三问就是允许在不同的方案中出现多次 a1 a_1 或 an a_n ， 这是我们只需要把与 f(1) f(1) 或 f(n) f(n) 相连的边的容量限制撤掉即可，即与其相连的边容量为 ∞ \infty ; 顺便吐槽一句出题人这里也没有解释清楚。。。

注意特判，如果第一问求得答案为 1 1 ，则直接输出 1 n n 1 \ n \ n 。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <new>
#include <queue>
#include <algorithm>
const int MAXN = 500;
struct Node;
struct Edge;
struct Node {
    Edge *e, *c;
    int level;
} N[MAXN * 2 + 10];
struct Edge {
    Node *fr, *to;
    Edge *ne, *rev;
    int cap, flow;
    Edge() {}
    Edge(Node *fr, Node *to, int cap) : fr(fr), to(to), ne(fr->e), cap(cap), flow(0) {}
};
inline void addEdge(int fr, int to, int cap) {
    N[fr].e = new Edge(&N[fr], &N[to], cap);
    N[to].e = new Edge(&N[to], &N[fr], 0);
    N[fr].e->rev = N[to].e, N[to].e->rev = N[fr].e;
}
struct Dinic {
    bool makeLevelGraph(Node *s, Node *t, int n) {
        for (int i = 0; i < n; i++) N[i].c = N[i].e, N[i].level = 0;
        std::queue<Node *> q;
        q.push(s);
        s->level = 1;
        while (!q.empty()) {
            Node *v = q.front();
            q.pop();
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->cap > e->flow && e->to->level == 0) {
                    e->to->level = v->level + 1;
                    if (e->to == t) return true;
                    q.push(e->to);
                }
            }
        }
        return false;
    }
    int findPath(Node *s, Node *t, int limit = INT_MAX) {
        if (s == t) return limit;
        for (Edge *&e = s->c; e; e = e->ne) {
            if (e->cap > e->flow && e->to->level == s->level + 1) {
                int flow = findPath(e->to, t, std::min(e->cap - e->flow, limit));
                if (flow > 0) {
                    e->flow += flow;
                    e->rev->flow -= flow;
                    return flow;
                }
            }
        }
        return 0;
    }
    int operator()(int s, int t, int n) {
        int res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            int flow;
            if ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
        }
        return res;
    }
} dinic;
int a[MAXN + 1], f[MAXN + 1], n, maxLength;
int subTask1() {
    int res = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 1; i <= n; i++) {
        int lastStat = 0;
        for (int j = 1; j < i; j++) {
            if (a[i] >= a[j] && lastStat < f[j]) lastStat = f[j];
        }
        f[i] = lastStat + 1;
        res = std::max(res, f[i]);
    }
    return res;
}
int subTask2() {
    const int s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; i++) {
        addEdge(i, i + n, 1);
        if (f[i] == maxLength) addEdge(i + n, t, 1);
        if (f[i] == 1) addEdge(s, i, 1);
        for (int j = 1; j < i; j++) {
            if (f[j] == f[i] - 1 && a[j] <= a[i]) addEdge(j + n, i, 1);
        }
    }
    int res = dinic(s, t, n * 2 + 2);
    return res;
}
int subTask3() {
    const int s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; i++) {
        int cap = 1;
        if (i == 1 || i == n) cap = INT_MAX;
        addEdge(i, i + n, cap);
        if (f[i] == maxLength) addEdge(i + n, t, cap);
        if (f[i] == 1) addEdge(s, i, cap);
        for (int j = 1; j < i; j++) {
            if (f[j] == f[i] - 1 && a[j] <= a[i]) addEdge(j + n, i, 1);
        }
    }
    int res = dinic(s, t, n * 2 + 2);
    return res;
}
int main() {
//	freopen("alis.in", "r", stdin);
//	freopen("alis.out", "w", stdout);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    printf("%d\n", maxLength = subTask1());
    if (maxLength == 1) {
        printf("%d\n%d", n, n);
    } else {
        printf("%d\n", subTask2());
        for (int i = 0; i < n * 2 + 2; i++) {
            for (Edge *&e = N[i].e, *ne; e; ne = e->ne, delete e, e = ne);
            N[i].e = N[i].c = NULL;
            N[i].level = 0;
        }
        printf("%d\n", subTask3());
    }
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}