想了一个多项式做法,至少能过 200200200。设序列长度是 O(n)O(n)O(n)。
其实就是要找到两个一样的子序列,且两个子序列首尾是隔开的。
那直接dp,f[i][j]f[i][j]f[i][j] 代表分别从 i,ji,ji,j 开始的,有多少子序列满足条件。这个显然可以 O(n)O(n)O(n) 转移。
但是两个子序列又要隔开,于是枚举第二个子序列开始的位置即可。那总的复杂度就是 O(n4)O(n^4)O(n4),常数很小肯定能冲 200200200。
感觉是有更低的复杂度的,欢迎来讨论。