摘自网络流 \(24\) 题官方题解。
第一问:直接 \(O(n^2)\) DP 求解最长不下降子序列即可。
第二问:
使用类似于 酒店之王 的思想,将点 \(i\) 拆成两个点 \(i_1\),\(i_2\)。然后 \(i_1\to i_2\) 的容量为 \(1\)。
如果有 \(i\in [1,n]\),\(f_i = 1\),那么 \(s\to i_1\) 连一条容量为 \(1\) 的边。
如果有 \(i\in[1,n]\),\(f_i = 最长不下降子序列的长度\),那么 \(i_2\to t\) 连一条容量为 \(1\) 的边。
如果是最长不下降子序列的转移,那么从 \(i_2\to j_1\) 的容量为 \(1\)。
然后求网络最大流即可。
第三问:
取消第一个点和最后一个点的流量限制即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], f[N], dep[N];
int n, s, t;
const int inf = 1e9 + 154;
struct edge
{
int e, f, opt;
edge() {}
edge (int a, int b)
{
this->e = a, this->f = b;
}
};
vector <edge> z[N];
vector <edge> ty[N];
void add(int s, int e, int f)
{
z[s].push_back(edge(e, f));
z[e].push_back(edge(s, 0));
int s1 = z[s].size() - 1, s2 = z[e].size() - 1;
z[s][s1].opt = s2;
z[e][s2].opt = s1;
}
bool bfs()
{
queue <int> q;
memset (dep, 0, sizeof dep);
dep[s] = 1;
q.push(s);
while (q.size())
{
int p = q.front();
q.pop();
for (auto &[r, f, g] : z[p])
if (f && !dep[r])
{
dep[r] = dep[p] + 1;
q.push(r);
if (r == t)
return true;
}
}
return false;
}
int dfs(int p, int f)
{
if (p == t)
return f;
int ans = 0;
for (int i = 0; i < z[p].size() && f; i ++)
{
int q = z[p][i].e;
int fx = z[p][i].f;
if (fx && dep[p] + 1 == dep[q])
{
int delta = dfs(q, min(f, fx));
z[p][i].f -= delta;
z[q][z[p][i].opt].f += delta;
f -= delta;
ans += delta;
}
}
if (!ans)
dep[p] = 0;
return ans;
}
int dinic()
{
int ans = 0;
while (bfs())
ans += dfs(s, inf);
return ans;
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
if (n == 1)
{
cout << "1\n1\n1\n";
return 0;
}
for (int i = 1; i <= n; i ++)
{
f[i] = 1;
for (int j = 1; j < i; j ++)
if (a[j] <= a[i])
f[i] = max(f[i], f[j] + 1);
}
int k = *max_element(f + 1, f + n + 1);
cout << k << '\n';
s = 2001, t = 2002;
for (int i = 1; i <= n; i ++)
if (f[i] == 1)
add(s, i, 1);
for (int i = 1; i <= n; i ++)
if (f[i] == k)
add(i + n, t, 1);
for (int i = 1; i <= n; i ++)
add(i, i + n, 1);
for (int i = 2; i <= n; i ++)
for (int j = 1; j < i; j ++)
if (a[i] >= a[j] && f[j] + 1 == f[i])
add(j + n, i, 1);
for (int i = 1; i <= 2002; i ++)
ty[i] = z[i];
cout << dinic() << '\n';
for (int i = 1; i <= 2002; i ++)
z[i] = ty[i];
add(1, n + 1, inf);
add(s, 1, inf);
if (f[n] == k)
{
add(n + n, t, inf);
add(n, n + n, inf);
}
// for (int i = 1; i <= 2002; i ++)
// z[i].clear();
// for (int i = 1; i <= n; i ++)
// if (f[i] == k)
// {
// if (i != 1 && i != n)
// add(s, i, 1);
// else
// add(s, i, inf);
// }
// for (int i = 1; i <= n; i ++)
// if (f[i] == 1)
// {
// if (i != 1 && i != n)
// add(i + n, t, 1);
// else
// add(i + n, t, inf);
// }
// for (int i = 1; i <= n; i ++)
// if (i != 1 && i != n)
// add(i, i + n, 1);
// else
// add(i, i + n, inf);
// for (int i = 2; i <= n; i ++)
// for (int j = 1; j < i; j ++)
// if (a[i] >= a[j] && f[j] + 1 == f[i])
// add(i + n, j, 1);
cout << dinic() << '\n';
return 0;
}
标签:洛谷,int,delta,dep,&&,ans,return,P2766,DP
From: https://www.cnblogs.com/lxylluvio/p/luogu2766.html