关于 LIS 问题的最短路解法
  • 板块学术版
  • 楼主Kingna
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/8/18 22:34
  • 上次更新2023/11/3 02:47:11
查看原帖
关于 LIS 问题的最短路解法
411727
Kingna楼主2023/8/18 22:34

LIS 题目是否可以用最短路算法?下面这个思路正不正确?

对于任意的 ai<aj,i<ja_i<a_j,i<j,从 ii 向 jj 连一条边权为 11 的有向边,并建立超级源点 00,从 00 向 i(1≤i≤n)i(1\leq i \leq n) 连一条边权为 00 的有向边。

从 00 开始跑 dijkstra,统计所有 dist[i] (1≤i≤n)(1\leq i \leq n) 最大值并加 11。

复杂度 O(n2log⁡n)O(n^2\log n) 。

2023/8/18 22:34
加载中...