#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int point[2100], next[2000003], v[2000003], remain[2000003]; int deep[2100], cur[2100], num[2100], n, m, tot, ans, laste[2100]; int a[2100], f[2100]; const int inf = 1e9; void add(int x, int y, int z) { tot++; next[tot] = point[x]; point[x] = tot; v[tot] = y; remain[tot] = z; tot++; next[tot] = point[y]; point[y] = tot; v[tot] = x; remain[tot] = 0; } int adde(int s, int t) { int now = t, minn = inf; while (now != s) { minn = min(minn, remain[laste[now]]); now = v[laste[now] ^ 1]; } now = t; while (now != s) { remain[laste[now]] -= minn; remain[laste[now] ^ 1] += minn; now = v[laste[now] ^ 1]; } return minn; } void bfs(int s, int t) { for (int i = s; i <= t; i++) deep[i] = t + 2; deep[t] = 0; queue<int> p; p.push(t); while (!p.empty()) { int now = p.front(); p.pop(); for (int i = point[now]; i != -1; i = next[i]) if (deep[v[i]] == t + 2 && remain[i ^ 1]) { deep[v[i]] = deep[now] + 1; p.push(v[i]); } } } int isap(int s, int t) { int flow = 0, now = s; bfs(s, t); memset(num, 0, sizeof(num)); for (int i = s; i <= t; i++) num[deep[i]]++; for (int i = s; i <= t; i++) cur[i] = point[i]; while (deep[s] <= t) { if (now == t) { flow += adde(s, t); now = s; } bool hasfind = false; for (int i = cur[now]; i != -1; i = next[i]) { if (deep[v[i]] + 1 == deep[now] && remain[i]) { hasfind = true; cur[now] = i; laste[v[i]] = i; now = v[i]; break; } } if (!hasfind) { int minn = t; for (int i = point[now]; i != -1; i = next[i]) if (remain[i]) minn = min(minn, deep[v[i]] + 1); if (!--num[deep[now]]) break; deep[now] = minn; num[minn]++; cur[now] = point[now]; if (now != s) now = v[laste[now] ^ 1]; } } return flow; } void solve1() { for (int i = 1; i <= n; i++) { if (f[i] == 1) add(0, i, 1); if (f[i] == ans) add(i + n, 2 * n + 1, 1); add(i, i + n, 1); } for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) if (f[i] == f[j] + 1 && a[i] >= a[j]) add(j + n, i, 1); } if (ans == 1) printf("%d ", n); else printf("%d ", isap(0, 2 * n + 1)); } void solve2() { tot = -1; memset(next, -1, sizeof(next)); memset(point, -1, sizeof(point)); for (int i = 1; i <= n; i++) { int v = 1; if (i == 1 || i == n) v = inf; if (f[i] == 1) add(0, i, v); if (f[i] == ans) add(i + n, 2 * n + 1, v); add(i, i + n, v); } for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) if (f[i] == f[j] + 1 && a[i] >= a[j]) add(j + n, i, 1); } if (ans == 1) printf("%d ", n); else printf("%d ", isap(0, 2 * n + 1)); } int main() { tot = -1; memset(next, -1, sizeof(next)); memset(point, -1, sizeof(point)); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); f[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) if (f[i] < f[j] && a[j] <= a[i]) f[i] = f[j]; f[i]++; } ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, f[i]); printf("%d ", ans); solve1(); solve2(); }
#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;int point[2100], next[2000003], v[2000003], remain[2000003];int deep[2100], cur[2100], num[2100], n, m, tot, ans, laste[2100];int a[2100], f[2100];const int inf = 1e9;void add(int x, int y, int z){tot++; next[tot] = point[x]; point[x] = tot; v[tot] = y; remain[tot] = z;tot++; next[tot] = point[y]; point[y] = tot; v[tot] = x; remain[tot] = 0;}int adde(int s, int t){int now = t, minn = inf;while (now != s){minn = min(minn, remain[laste[now]]);now = v[laste[now] ^ 1];}now = t;while (now != s){remain[laste[now]] -= minn;remain[laste[now] ^ 1] += minn;now = v[laste[now] ^ 1];}return minn;}void bfs(int s, int t){for (int i = s; i <= t; i++)deep[i] = t + 2;deep[t] = 0;queue<int> p;p.push(t);while (!p.empty()){int now = p.front(); p.pop();for (int i = point[now]; i != -1; i = next[i])if (deep[v[i]] == t + 2 && remain[i ^ 1]){deep[v[i]] = deep[now] + 1;p.push(v[i]);}}}int isap(int s, int t){int flow = 0, now = s;bfs(s, t);memset(num, 0, sizeof(num));for (int i = s; i <= t; i++) num[deep[i]]++;for (int i = s; i <= t; i++) cur[i] = point[i];while (deep[s] <= t){if (now == t){flow += adde(s, t);now = s;}bool hasfind = false;for (int i = cur[now]; i != -1; i = next[i]){if (deep[v[i]] + 1 == deep[now] && remain[i]){hasfind = true;cur[now] = i;laste[v[i]] = i;now = v[i];break;}}if (!hasfind){int minn = t;for (int i = point[now]; i != -1; i = next[i])if (remain[i])minn = min(minn, deep[v[i]] + 1);if (!--num[deep[now]]) break;deep[now] = minn;num[minn]++; cur[now] = point[now];if (now != s)now = v[laste[now] ^ 1];}}return flow;}void solve1(){for (int i = 1; i <= n; i++){if (f[i] == 1) add(0, i, 1);if (f[i] == ans) add(i + n, 2 * n + 1, 1);add(i, i + n, 1);}for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++)if (f[i] == f[j] + 1 && a[i] >= a[j])add(j + n, i, 1);}if (ans == 1) printf("%d ", n);elseprintf("%d ", isap(0, 2 * n + 1));}void solve2(){tot = -1; memset(next, -1, sizeof(next)); memset(point, -1, sizeof(point));for (int i = 1; i <= n; i++){int v = 1;if (i == 1 || i == n) v = inf;if (f[i] == 1) add(0, i, v);if (f[i] == ans) add(i + n, 2 * n + 1, v);add(i, i + n, v);}for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++)if (f[i] == f[j] + 1 && a[i] >= a[j])add(j + n, i, 1);}if (ans == 1) printf("%d ", n);elseprintf("%d ", isap(0, 2 * n + 1));}int main(){tot = -1; memset(next, -1, sizeof(next)); memset(point, -1, sizeof(point));scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);f[1] = 1;for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++)if (f[i] < f[j] && a[j] <= a[i])f[i] = f[j];f[i]++;}ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, f[i]);printf("%d ", ans);solve1();solve2();}