给定一个长度为 \(n\) 的序列 \(a\) ，你需要翻转一段区间 \([l,r]\) 来最大化序列的最长不下降子序列。
求出最长不下降子序列长度以及翻转的区间。
数据范围: \(1\le n\le 10^5, 0\le a_i\le 9\)
Solution
枚举 \([x,y]\) 表示翻转区间内产生贡献的数的值域范围，设 \(b = \{ 0...x, y...x, y...9\}\) ，然后跑 \(a\) 和 \(b\) 的 \(LCS\) 即可，这里的 \(b\) 的数可多次被覆盖。
定义 \(dp[i][j]\) 表示 \(a\) 到 \(i\) , \(b\) 到 \(j\) 的 \(LCS\) ，显然有
枚举的过程中顺带维护 翻转区间的两端点 即可。
时间复杂度: \(O(45*12*n)\) ，跑不满。
原文：https://www.cnblogs.com/wlzhouzhuan/p/13341777.html