LIS 题目是否可以用最短路算法?下面这个思路正不正确?
对于任意的 ai<aj,i<ja_i<a_j,i<jai<aj,i<j,从 iii 向 jjj 连一条边权为 111 的有向边,并建立超级源点 000,从 000 向 i(1≤i≤n)i(1\leq i \leq n)i(1≤i≤n) 连一条边权为 000 的有向边。
从 000 开始跑 dijkstra,统计所有 dist[i] (1≤i≤n)(1\leq i \leq n)(1≤i≤n) 最大值并加 111。
复杂度 O(n2logn)O(n^2\log n)O(n2logn) 。