【魔怔】拼接。记忆。破碎。

你是一名因水平原因而遗憾退役的 OIer。退役之际，你正努力寻找和拼接着你在 OI 生涯中的回忆。

按顺序，你有 $n$ 片关于 OI 的记忆，每一片用一个数字 $a_i(1\le a_i\le 20)$ 代表，数字相同代表记忆内容相近。

你想把其中最具有代表性的记忆拼接在一起，可以不在原序列中连续。具体地，你要求出一个 $a$ 的可不连续的子序列，其中两片相近的记忆（ $a_i=a_j$ ）需要在子序列中连续。同时，你不想让过多重复的记忆进入，所以每一片记忆的内容只会出现 $0$ 次或 $2$ 次。

请求出你所获得的回忆子序列的最长长度。

你马上想到，可以使用状压求出分别是否选择了

20

种内容。记

S

为当前状态的二进制值，从低到高第

i

位为

1

代表已经被选择，为

0

代表未被选择。

你考虑从小到大枚举

S

，并记录能达到这种状态的最小的下标

f_i

（如果无法达到，

f_i=\infty

）。你很显然地发现，对于一个状态

S

，通过枚举往后延展回忆的内容编号（

1\sim 20

）来进行转移即可高效地完成。

具体地，设当前状态为

S

（

f_S\ne \infty

），被延展的回忆内容编号为

x

（

S

开始时从低到高第

i

位不能为

1

），则新状态的编号为

S'=S+2^{x-1}

。

S

能够向

S'

转移的充要条件，即是在

f_S

之后，仍然有两个下标

j,k

满足

a_j=a_k=a_{f_i}

，且

k<f_{S'}

，则此时即可让

f_{S'}=k

。

你也发现暴力地求出

j,k

是低效的，于是你预处理了一个

nxt_{i,j}

，代表从下标

i

开始下一个值为

j

的下标，于是解决了这道题。

你的代码。

你成功地把你 OI 生涯中最具代表性的事物留在了脑海中，可你却仍感空虚。仅用至多

40

片回忆来代表这近乎数万的记忆，未免有所片面。因为，你的 OI 生涯里有太多美好。

回望这些回忆，你忽而感到它们在破碎。正因缺少了什么，或是前因后果，或是平凡琐事，你感觉它们都失去了意义。越往深入去想，你的自我怀疑越深，情绪也越崩溃。可于千钧一发之际，你似乎找到了一切的答案，它能够串联起你的整个 OI 生涯，不遗留，也无遗憾。

这就是你热爱 OI 的心。

【魔怔】拼接。记忆。破碎。

文章操作

相关推荐

评论

【魔怔】拼接。记忆。破碎。