2565: SubRaY未出现的子串

admin

[说明]此题中的子数字串,数字并不一定连续出现在母数字串中.比如我们定义1 3是串1 5 3的一个子串,但3 5不是1 5 3的一个子串.
串1 5 3的所有子串为:
1
5
3
1 5
5 3
1 3
1 5 3
共7个.
[题目描述]有一个长度为n的数字串,其中会出现数字1,2,3,...,q(5<=q<=9).SubRaY遇到的问题是,需要求出一个长度最小的串(出现的数字也是1..q),使得该串不是这个数字串的子串.为了简化问题,你只需要输出这个串的长度即可.

例如对于数字串S=
1 3 5 2 4 1 3 5 2 2 2 2 3 4 1 5 3 2(q=5)

长度为1和2的数字子串全出现过,但是你找不出子串S'=4 4 4.因此答案是3

[输入][unapeared.in]
第一行两个数,串长n和出现的数字的个数q
接下来n行表示该数字串每一位的数字.

[输出][unapeared.out]
未出现的子串的最小长度

[样例输入]
18 5
1
3
5
2
4
1
3
5
2
2
2
2
3
4
1
5
3
2

[样例输出]

3

[数据范围]

对于30%的数据,1<=n<=20,q=5
对于100%的数据,1<=n<=100000,5<=q<=9

admin

解法1 搜索

可以证明,要判断一个数列3,5,1是否在母数列中出现过,可以先找出3在母数列中最先出现的地方,然后从这个地方开始,找5最先出现的地方,然后再找这个地方之后1最先出现的地方,如果都能找到,则该串是这个母串的子串,否则不是.

因此可以预先做一个预处理,用next[I,j]表示从母串第i个数字开始,数字j最先出现在母串的第几个元素处.然后长度不断加一,逐个构造当前长度的字串并判断是否为母串的一个子串,当搜索到第一个非子串时跳出.这就是所谓的DFS-ID(迭代加深搜索).

预处理的时间复杂度为O(nq),这个思想很值得借鉴.

解法2 DP-O(nq)

在解法1枚举长度时,可以随时保存当前符合的子串的最长长度,当长度加一时,只需从这个长度开始就可以了.这个叫记忆化搜索,也即DP

或者,用f(i,j)表示长度为i,最后一个数字为j的子串最早结束于母串的什么位置,那么状态转移方程为:f(i,j)=max{f[i-1,j]}+next[max{f[i-1,j]},j].