学步园

题目:未出现的子串 

题目描述

[说明]此题中的子数字串,数字并不一定连续出现在母数字串中.比如我们定义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
[数据范围]
对于30%的数据,1<=n<=20,q=5
对于100%的数据,1<=n<=100000,5<=q<=9

输入格式

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

输出格式

未出现的子串的最小长度

样例输入

18 5

1

3

5

2

4

1

3

5

2

2

2

2

3

4

1

5

3

2

样例输出

 3

 

注：这道题目可以有两种解法。第一种是DP：我们首先定义匹配的定义：一个合法的子串，对于每一个数字，如果后面从1-q每一个数字都能成功做到不少于长度为k的匹配，那么这个数字的成功匹配长度就是k+1，于是有了状态转移方程：f[i]=min{f[k]}+1; (i ∈[1..q],k>i)。由于是寻找后面的匹配长度，所以要进行倒推；第二种方法是数学中的集合思想，我们将这个数字序列分成k份，保证每一份中含有1..q并且最多分成k份，那么最后的答案就是k+1。

代码1：

var
  a:array[0..100000] of longint;
  f:array[0..9] of longint;
  i,j,k,ans,n,q:longint;

function min(x,y:longint):longint;
begin
  if x<y then exit(x);
  exit(y);
end;

function max(x,y:longint):longint;
begin
  if x>y then exit(x);
  exit(y);
end;

begin
  readln(n,q);
  for i:=1 to n do readln(a[i]);
  ans:=0;
  for i:=n downto 1 do
    begin
      k:=maxlongint;
      for j:=1 to q do
        k:=min(k,f[j]);
      f[a[i]]:=k+1;
    end;
  for i:=1 to q do
    ans:=max(ans,f[i]);
  writeln(ans);
end.

代码2：

var
  i,j,k,ans,n,m,q:longint;
  vv:boolean;
  v:array[0..10] of boolean;
begin
  readln(n,q);
  ans:=1;
  fillchar(v,sizeof(v),false);
  for i:=1 to n do
    begin
      vv:=true;
      for j:=1 to q do
        if not v[j] then
          begin
            vv:=false;
            break;
          end;
      if vv then
        begin
          fillchar(v,sizeof(v),false);
          inc(ans);
        end;
      readln(k);
      v[k]:=true;
    end;
  writeln(ans);
end.