hydd的博客

博客

Array Solution

2020-05-14 17:05:38 By hydd

考虑从左往右逐个加入数字,如果线索必须是从左往右怎么做?首先考虑状压已经出现过的线索,线索出现的位置可能重叠,那么我们考虑一条线索开始时的位置,此时若有别的线索还没结束,那么一定需要满足完成新的线索之时或之前能够完成旧的线索。

设 $f(S,i,j)$ 为已经出现了线索集合 $S$ ,当前最后一个开始的线索为 $i$ 且匹配到第 $j$ 位时最短的序列长度,预处理 $a(i,j,k)$ 表示匹配到第 $i$ 条线索的第 $j$ 位时能否换到第 $k$ 条线索进行匹配。

转移时往下再匹配,或者枚举一条新的满足条件的线索,这是一个边权只有 0 和 1 的最短路,时间复杂度 $O(n^2 \cdot 2^n)$。

如果只有从右往左的线索呢,从左往右的时候我们考虑线索开始的时刻,那么现在就考虑线索结束的时刻,结束的时候枚举下一条线索计算最多能够重叠多少,即记 $b(i,j)$ 为第 $i$ 条线索结束时接第 $j$ 条线索最多可以匹配到第 $j$ 条线索的第几位,状态和转移类似,时间复杂度 $O(n^2 \cdot 2^n)$。

接下来就是考虑如何把向左的和向右的结合在一起,设 $f(S,i,j,k,l)$ 为当前出现了集合 $S$ 中的线索,从左到右的第 $i$ 条线索匹配到第 $j$ 位,从右到左的第 $k$ 条线索匹配到第 $l$ 位的答案,特殊地当 $i$ 或 $k$ 等于 0 表示当前没有这个方向的线索正在匹配。转移的时候往一边扩展一位,或者枚举一个新的线索替换某一跟方向的线索,注意扩展一位的时候处理好另一个方向的变化,同样是边权为 0/1 的最短路。时间复杂度 $O(n^3 \cdot 2^n)$。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。