[GESP样题七级] 最长不下降子序列

题目描述

小杨有个包含 $n$ 个节点 $m$ 条边的有向无环图，其中节点的编号为 $1$ 到 $n$ 。

对于编号为 $i$ 的节点，其权值为 $A_i$ 。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。

注：给定一个序列 $S$ ，其最长不下降子序列 $S'$ 是原序列中的如下子序列：整个子序列 $S'$ 单调不降，并且是序列中最长的单调不降子序列。例如，给定序列 $S = [11,12,13,9,8,17,19]$ ，其最长不下降子序列为 $S'=[11,12,13,17,19]$ ，长度为 $5$ 。

输入格式

第一行包含两个正整数 $n,m$ ，表示节点数和边数。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots A_n$ ，表示节点 $1$ 到 $n$ 的点权。

之后 $m$ 行每行包含两个正整数 $u_i, v_i$ ，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$ ，方向为从 $u_i$ 到 $v_i$ 。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

6 11
1 1 2 1 1 2
3 2
3 1
5 3
4 2
2 6
3 6
1 6
4 6
1 2
5 1
5 4

输出 #2

输入输出样例 #3

输入 #3

6 11
5 9 10 5 1 6
5 4
5 2
4 2
3 1
5 3
6 1
4 1
4 3
5 1
2 3
2 1

输出 #3

说明/提示

数据规模与约定

子任务	分值	$n\le$	$A_i \le$	特殊约定
$1$	$30$	$10^3$	$10$	输入的图是一条链
$2$	$30$	$10^5$	$2$	无
$3$	$40$	$10^5$	$10$	无

对全部的测试数据，保证 $1 \leq n \leq 10^5$ ， $1 \leq m \leq 10^5$ ， $1 \leq A_i \leq 10$ 。

题目分析

目的：图中所有可能序列中最长不下降子序列的最大长度。

可概括得到这是一个最长上升子序列的变形问题。首先回顾下最长上升子序列问题，设dp[i]表示第i个元素结尾的最长上升子序列的长度，那么有状态转移方程：

dp[i] = \max\limits_{1 \leq j < i, A_j < A_i} { (dp[j]) } + 1

这道题目中特殊之处在于，这是一个在图上的问题，我们需要在图这样的非线性结构中进行动态规划，可以联想到在图上进行动态规划的方法，即拓扑排序。本道题已明确为有向无环图，因此可以使用拓扑排序进行动态规划。

另外，针对当前序列结尾元素 a[v]，我们需要枚举所有在它前面、结尾小于等于它的子序列。此时在非线性结构中遍历之前所有的元素不太现实，但是可观察到数值范围为 $[1,10]$ ，是比较小的，因此可以遍历所有可能的结尾值为 $1\sim a[v]$ 的子序列。

设 dp[v][x]表示以结点v为结尾的子序列中，结尾为x的最长不下降子序列的长度，状态转移方程为：

dp[v][a_v] = \max\limits_{1 \leq j \le a_v} { (dp[u][j]) } + 1 \\ dp[v][x]_{x\neq a_v}= dp[u][x]

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5;
int n,m;
int a[N];
vector<int> G[N];
int in[N];
int dp[N][15];
void topu(){
  queue<int> q;
  for(int i=1;i<=n;i++){
    if(!in[i]){
      q.push(i);
      dp[i][a[i]]=1;
    }
  }
  while(!q.empty()){
    int u=q.front();
    q.pop();
    for(int v:G[u]){
      in[v]--;
      int maxs=0;
      for(int i=1;i<=10;i++){
        dp[v][i]=max(dp[v][i],dp[u][i]);
        if(i<=a[v]) maxs=max(maxs,dp[u][i]+1);
      }
      dp[v][a[v]]=max(dp[v][a[v]],maxs);
      if(!in[v]){
        q.push(v);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  for(int i=1;i<=m;i++){
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);
    in[v]++;
  }
  topu();
  int ans=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=10;j++){
      ans=max(ans,dp[i][j]);
    }
  }
  cout<<ans;
  return 0;
}

[GESP样题 七级] 最长不下降子序列