自动搬运

查看原文

来自洛谷，原作者为

	LionBlaze @wsx 我这么弱你还说我批话/ll || 有实力或没那么有实力的欢迎加入 WROI /team/96917 || 前置声明：不当除了 WROI 之外任何公开赛的背锅人。接受私信协商。

搬运于2025-08-24 22:56:33，当前版本为作者最后更新于2024-06-19 20:11:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其实我一开始看到也是拓扑排序 + DP，并且和 spfa_ 大佬最后的结论一样，但会更详细点。

为什么要拓扑排序？

小杨有个包含 $n$ 个节点 $m$ 条边的有向无环图。
根据路径上的经过节点的先后顺序可以得到一个节点权值的序列。

正是拓扑排序的拿手好戏。

DP 开始

定义

第一种

直接套，$f_i$ 表示从某个点到点 $i$，最长不下降子序列的最大长度。

然后每遇到一条边就更新一次。

然后……就没有然后了。$\color{white}{\texttt{吗？}}$

时间复杂度：一共 $m$ 条边，每条边转移时间复杂度为 $O(n)$，总时间复杂度为 $O(nm)$，毫无疑问会 TLE。

看来不行。

第二种

抓住题目的“弱点”，发现一个很奇怪的条件，$1 \le A_i \le 10$。

所以可以成为 $f$ 的第二维：

$f_{i,j}$ 代表从某个点开始，到点 $i$，满足最后一个数字为 $j$ 的最长不下降子序列的最大长度。

初始状态

所有 $f_{i,A_i} = 1$：只有当前点。

转移顺序

拓扑序，如果不是，在转移当前点时可能某个前驱节点还没转移到，如果从那个节点转移到这个节点刚好是最优解（或者最优解的一部分），答案就会出错。

状态转移方程

重点来了！

对于点 $v$ 的某一个前驱结点 $u$（或者对于点 $u$ 的某个后继结点 $v$），有两种转移：

第一种

一种是将点 $v$ 加入到点 $u$ 的最长不下降子序列中，比如：

此时点 $u$ 的最长不下降子序列为 $1,2,3$（即 $f_{u,3} = 3$），而 $A_v \ge 3$，则这种转移会使 $f_{v, A_v} = f_{u, 3} + 1 = 4$，前提是原 $f_{v, A_v} < 4$（不然得到更劣的解）。

不难知道：

$$\forall 1 \le i \le A_v:f_{v, A_i}=\max(f_{v, A_i}, f_{u, i} + 1) $$

右边很好理解。左边为什么是 $1 \le i \le A_v$ 呢？不可以大于 $A_v$ 吗？

不可以。

因为在不下降序列的末尾增加一个比原来的末尾更小的元素，增加后就不是不下降序列了。

比如你在不下降序列 $1,2,3$ 最后加入一个 $2$，最后还满足不下降吗？显然不满足。

第二种

第二种就是不算上元素 $v$，本来是 $1,2,3$ 现在还是 $1,2,3$，子序列嘛，可以去除某些元素（这里是去除元素 $v$）。

$$\forall 1 \le i \le 10 : f_{v,i} = \max(f_{v,i},f_{u,i}) $$

答案

所有有意义的 $f_{i,j}$ 的最大值（有意义：$1\le i \le n$，$1 \le j \le 10$）

完结撒花~代码

#include <queue>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> web[100005]; //邻接表
int a[100005]; //A
int ind[100005]; //入度
int f[100005][15];
/*
f[i][j] 代表从xxx节点到i节点，末尾为j的最长不下降子序列长度
*/

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d", a + i);
	}
	for(int i=1;i<=m;i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		web[u].push_back(v); //建图
		ind[v]++; //入度++
	}
	queue<int> q; //拓扑排序
	for(int i=1;i<=n;i++)
	{
		if(ind[i] == 0) //入度为0，进队
		{
			q.push(i);
		}
		f[i][a[i]] = 1; //f初始
	}
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int v : web[u])
		{
			if(!--ind[v]) q.push(v); //入度变为0
			for(int i=1;i<=a[v];i++)
			{
				if(f[u][i] + 1 > f[v][a[v]]) f[v][a[v]] = f[u][i] + 1; //第一种转移
			}
			for(int i=1;i<=10;i++)
			{
				if(f[u][i] > f[v][i]) f[v][i] = f[u][i]; //第二种转移
			}
		}
	}
	int maxn = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=10;j++)
		{
			if(f[i][j] > maxn) maxn = f[i][j]; //取最大
		}
	}
	printf("%d\n", maxn);
	return 0;
}