yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P2766 最长不下降子序列问题

发表于 更新于 分类于

P2766 最长不下降子序列问题

题面

题目链接

解法

第一问直接$O(n^2)$求。

第二问根据第一问$dp$的合法转移建立$DAG$图，拆点并求出最大流。即对于$\forall a_j \le a_i, dp_i = dp_j + 1$，连接$j_1 \to i_0$，流量为$1$，且连接每个$i_0 \to i_1$。如果$dp_i=1$则连接$S \to i_0$，$dp_i=ans_1$则连接$i_1 \to T$。这样就保证了每次增广都找到一个长度最长的子序列，并且每个点只能取一次。

第三问由于$1$和$n$无限制，所以将$S \to 1$和$n \to T$（如果有）的流量改为$+\infty$，并将$1_0 \to 1_1$和$n_0 \to n_1$也改为$+\infty$即可。注意要特判$n=1$。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
 * @file:           P2766.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P2766
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 2e3 + 10;
const int MAXM = 5e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
    struct Edge {
        int v, flow;
    } edge[MAXM];
    int tot = 1, flow = 0;
    int head[MAXN], nxt[MAXM], lev[MAXN], cur[MAXN];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        memset(lev, -1, sizeof(lev));
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            memcpy(cur, head, sizeof(cur));
            flow += augment(s, t, INF);
        }
        return flow;
    }
};
int n, s, t, num, a[MAXN], dp[MAXN], pt[MAXN][2];
Dinic network;
signed main() {
    read(n);
    int ans1 = 0, ans2 = 0, ans3 = 0;
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] <= a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    }
    ans1 = *max_element(dp + 1, dp + n + 1);
    s = ++num, t = ++num;
    for (int i = 1; i <= n; ++i) {
        pt[i][0] = ++num, pt[i][1] = ++num;
        network.addedge(pt[i][0], pt[i][1], 1);
        if (dp[i] == 1)
            network.addedge(s, pt[i][0], 1);
        if (dp[i] == ans1)
            network.addedge(pt[i][1], t, 1);
        for (int j = 1; j < i; ++j)
            if (a[j] <= a[i] && dp[j] + 1 == dp[i])
                network.addedge(pt[j][1], pt[i][0], 1);
    }
    ans2 = network.maxflow(s, t);
    if (dp[1] == 1)
        network.addedge(s, pt[1][0], INF - 1);
    if (dp[n] == ans1)
        network.addedge(pt[n][1], t, INF - 1);
    network.addedge(pt[1][0], pt[1][1], INF - 1);
    network.addedge(pt[n][0], pt[n][1], INF - 1);
    ans3 = (n == 1) ? 1 : network.maxflow(s, t);
    write(ans1), putchar('\n');
    write(ans2), putchar('\n');
    write(ans3), putchar('\n');
    return 0;
}