题解：P10287 [GESP样题 七级] 最长不下降子序列
LionBlaze
·
·
题解
其实我一开始看到也是拓扑排序 + 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,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$）
## 完结撒花~代码
```cpp
#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;
}
```