Phát biểu bài toán

Cho dãy số nguyên dương \( x_1, x_2, \ldots, x_n \).

1. Tính độ dài \( s \) của dãy con không giảm dài nhất.
2. Tính số lượng tối đa các dãy con không giảm độ dài \( s \) có thể trích xuất từ dãy ban đầu, sao cho mỗi phần tử chỉ được dùng một lần.
3. Nếu cho phép sử dụng lại phần tử đầu tiên \( x_1 \) và phần tử cuối cùng \( x_n \), hỏi có thể trích xuất được tối đa bao nhiêu dãy con như vậy?

Định dạng nhập/xuất

Dữ liệu vào:

• Dòng đầu chứa số nguyên \( n \) – độ dài dãy.
• Dòng tiếp theo gồm \( n \) số nguyên \( x_1, x_2, \ldots, x_n \).

Dữ liệu ra:

• Dòng 1: Độ dài \( s \) của dãy con không giảm dài nhất.
• Dòng 2: Số lượng dãy con tối đa (mỗi phần tử dùng một lần).
• Dòng 3: Số lượng dãy con tối đa nếu \( x_1 \) và \( x_n \) được dùng nhiều lần.

Ví dụ minh họa

4
3 6 2 5

2
2
3

Phân tích và hướng giải

Để giải quyết ba yêu cầu, ta chia bài toán thành các bước:

Bước 1: Tính độ dài dãy con không giảm dài nhất

Sử dụng quy hoạch động để tính \( f[i] \): độ dài lớn nhất của dãy con không giảm bắt đầu tại vị trí \( i \). Ta duyệt ngược từ cuối dãy:

for (int i = n; i >= 1; i--) {
    f[i] = 1;
    for (int j = i + 1; j <= n; j++) {
        if (x[i] <= x[j]) {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    s = max(s, f[i]);
}

Bước 2: Mô hình hóa bằng luồng mạng (Luồng cực đại)

Chúng ta sẽ xây dựng đồ thị luồng để mô phỏng việc chọn các dãy con rời nhau.

• Mỗi đỉnh \( i \) được tách thành hai đỉnh: \( u_i \) (vào) và \( v_i \) (ra).
• Thêm cạnh \( u_i \to v_i \) với sức chứa 1 (đảm bảo mỗi phần tử dùng một lần).
• Nếu \( x[i] \leq x[j] \) và \( f[i] = f[j] + 1 \), thêm cạnh \( v_i \to u_j \) với sức chứa 1.
• Các đỉnh có \( f[i] = s \) nối từ nguồn \( S \to u_i \) với sức chứa vô hạn.
• Các đỉnh có \( f[i] = 1 \) nối tới đích \( v_i \to T \) với sức chứa vô hạn.

Giá trị luồng cực đại trên đồ thị này chính là số lượng dãy con tối đa trong câu (2).

Bước 3: Cho phép dùng lặp \( x_1 \) và \( x_n \)

Chỉ cần thay đổi sức chứa của các cạnh tương ứng với vị trí 1 và \( n \): cạnh \( u_1 \to v_1 \) và \( u_n \to v_n \) được đặt sức chứa vô hạn. Các cạnh khác giữ nguyên.

Xử lý đặc biệt

Khi \( s = 1 \), mọi phần tử đều có thể đứng riêng lẻ làm một dãy con. Do đó kết quả của cả hai câu sau đều là \( n \).

Cài đặt thuật toán Dinic

Dưới đây là mã nguồn hoàn chỉnh với mô hình luồng đã nêu:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXM = 300000;
const int INF = 1e9;

int n, s = 0;
int x[MAXN], f[MAXN];
int h[MAXN], to[MAXM], nxt[MAXM], fl[MAXM], etop = 0;
int lev[MAXN];
queue<int> q;

void addEdge(int u, int v, int w) {
    to[etop] = v; fl[etop] = w; nxt[etop] = h[u]; h[u] = etop++;
    to[etop] = u; fl[etop] = 0;  nxt[etop] = h[v]; h[v] = etop++;
}

bool bfs(int S, int T) {
    memset(lev, -1, sizeof(lev));
    lev[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int k = h[u]; k != -1; k = nxt[k]) {
            int v = to[k];
            if (lev[v] == -1 && fl[k] > 0) {
                lev[v] = lev[u] + 1;
                q.push(v);
            }
        }
    }
    return lev[T] != -1;
}

int dfs(int u, int T, int flowIn) {
    if (u == T) return flowIn;
    int flowOut = 0;
    for (int k = h[u]; k != -1; k = nxt[k]) {
        int v = to[k];
        if (lev[v] == lev[u] + 1 && fl[k] > 0) {
            int f = dfs(v, T, min(flowIn - flowOut, fl[k]));
            if (f > 0) {
                fl[k] -= f;
                fl[k^1] += f;
                flowOut += f;
                if (flowOut == flowIn) break;
            }
        }
    }
    return flowOut;
}

int dinic(int S, int T) {
    int totalFlow = 0;
    while (bfs(S, T)) {
        while (int f = dfs(S, T, INF)) {
            totalFlow += f;
        }
    }
    return totalFlow;
}

void buildGraph(bool infiniteFirstLast) {
    memset(h, -1, sizeof(h));
    etop = 0;
    int S = 0, T = 2 * n + 1;

    for (int i = 1; i <= n; i++) {
        int cap = (infiniteFirstLast && (i == 1 || i == n)) ? INF : 1;
        addEdge(i * 2, i * 2 + 1, cap);

        if (f[i] == s) {
            addEdge(S, i * 2, INF);
        }
        if (f[i] == 1) {
            addEdge(i * 2 + 1, T, INF);
        }

        for (int j = i + 1; j <= n; j++) {
            if (x[i] <= x[j] && f[i] == f[j] + 1) {
                addEdge(i * 2 + 1, j * 2, 1);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x[i]);
    }

    // Bước 1: Tính f[i] và s
    for (int i = n; i >= 1; i--) {
        f[i] = 1;
        for (int j = i + 1; j <= n; j++) {
            if (x[i] <= x[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        s = max(s, f[i]);
    }

    printf("%d\n", s);

    if (s == 1) {
        printf("%d\n%d\n", n, n);
        return 0;
    }

    // Câu 2: Mỗi phần tử dùng một lần
    buildGraph(false);
    int ans2 = dinic(0, 2 * n + 1);
    printf("%d\n", ans2);

    // Câu 3: Cho phép dùng lặp x1 và xn
    buildGraph(true);
    int ans3 = dinic(0, 2 * n + 1);
    printf("%d\n", ans3);

    return 0;
}