[GESP样题 七级] 最长不下降子序列题解
题目传送门题目大意
给定一个有向图无环图\(G\)，在这个图中寻找一条路径，是这条路径上的点权所组成的序列的最长不下降子序列的长度最长。
思路部分
解决无后效性
求一个有向无环图中的最长不下降子序列，不难想到这应该是一个图上dp，而在一个图中我们没法保证编号\(1\)到\(N\)去计算一定是满足了无后效性的，所以我们考虑找到一个顺序，这个顺序满足无后效性。
而在有向无环图中寻找一个序列，这个序列满足对于任意\(i(1≤i≤n)\)，小于\(i\)的所有节点都在\(i\)的左边（或一样），大于\(i\)的所有节点都在\(i\)的右边（或一样）。
根据上述定义，不难看出这是这个有向图的拓扑序列。拓扑序的求法如下：
[*]找到入度为\(0\)的点，入队。
[*]重复执行直到队列为空，从队首取出一个元素\(u\)，枚举这个点能够到达的点\(v\)，把点\(v\)的入度减一，判断如果点\(v\)的入度为0，那么入队。
在求拓扑序时，已经满足了无后效性这个条件，所以我们直接在这个过程中对答案求解。
解决动态规划
接着，我们讨论该如何对答案进行求解。
考虑在线性元素中对最长不下降子序列求解的定义为：以第\(i\)个元素为结尾的最长长度。那么我们是否能再次运用这个定义呢？
答案是肯定不行。第一：时间复杂度接受不了\(o(N^2)\)会炸。第二：我们无法知道以更加前面的节点为结尾的最长长度。
那么我们该如何求解呢？
根据数据范围可知，虽然点和边的数量很大，但是每个节点的点权很小，最大也就才\(10\)。所以我们可以想出以节点\(i\)，点权为\(j\)结尾的最长子序列。这时，我们不需要直到之前的节点了，只需要枚举颜色是什么即可。而转移方程类似于背包，代码入下：
for(int i = 1; i
页:
[1]