Codeforces Round 264 (Div. 2) D题 Gargari and Permutations（建图，有向无环图求最长路）

题目链接

Codeforces Round 264 (Div. 2) D题 Gargari and Permutations

思路

我们发现，$n$最大为$1e3$，这是一个很小的数。

若在所有的排列中，每一对$i$都在$j$的左边，则在公共子序列中存在$i$向$j$的转移。

因此我们可以对所有满足条件的$(i,j)$连一条有向边，容易发现建成的图是一个即有向无环图（DAG），只需要求出DAG的最长路即可。

在这里，我们采用拓扑排序和dp进行求解。

关于有向无环图（DAG）的参考资料：DAG-oiwiki

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int n, k;
int du[N], dist[N];
vector<int>g[N];
void solve()
{
cin >> n >> k;
vector<vector<int>>mp(k + 1, vector<int>(n + 1, 0));
vector<vector<int>>pos(k + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> mp[i][j];
pos[i][mp[i][j]] = j;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j) continue;
bool ok = true;
for (int num = 1; num <= k; num++)
{
if (pos[num][i] < pos[num][j])
ok = false;
}
if (ok)
{
du[i]++;
g[j].push_back(i);
}
}
}

queue<int>q;
for (int i = 1; i <= n; i++)
{
if (!du[i]) q.push(i);
}
vector<int>topsort;
while (q.size())
{
int u = q.front();
topsort.push_back(u);
q.pop();
for (int j : g[u])
{
du[j]--;
if (!du[j])
q.push(j);
}
}
for (int u : topsort)
{
for (int v : g[u])
{
dist[v] = max(dist[v], dist[u] + 1);
}
}
cout << *max_element(dist + 1, dist + 1 + n) + 1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/142745762

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！