提交次数 : 10    通过次数 : 6
题目描述
此题中的子数字串,数字并不一定连续出现在母数字串中.比如我们定义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
输入描述
第一行两个数,串长n 和出现的数字的个数q
接下来n 行表示该数字串每一位的数字.
对于30%的数据,1<=n<=20,q=5
对于100%的数据,1<=n<=100000,5<=q<=9
输出描述
未出现的子串的最小长度
样例输入
18 5
1
3
5
2
4
1
3
5
2
2
2
2
3
4
1
5
3
2
样例输出
3


求思路和C语言代码

[ 本帖最后由 草狼 于 2010-4-16 16:00 编辑 ]

这个可以用比动态规划更好的方法解决....

算法：
1.从字串开始 查找 1 到q的所有的数字 并 记录此时的位置为m，并定义为一轮 c=1
2.从m+1开始继续查找 1 到 q 的所有数字 替换m的位置，c++, 直到 到字串的末尾 记录总共的轮数
3.最终的c＋1就是需要输出的结果

代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,j,n,q,c=0,sum=0;
    int *s,*u_s;
    scanf("%d %d\n",&n,&q);

    s = (int *)malloc(n*sizeof(int));
    u_s = (int *)calloc(q+1,sizeof(int));

    for (i=0;i<n ;i++ )
        scanf("%d",s+i);

    for (i=0;i<n ;i++ )
    {
        if (u_s[s[i]]==0)
        {
            u_s[s[i]]=1;
            sum++;
        }
        if (sum == q)
        {
            c++;
            sum=0;
            for (j=0;j<q+1 ;j++ )
                u_s[j]=0;
        }

    }

    c++;
    printf("%d\n",c);

    return 0;
}

结果：

D:\c_sources_bak\bbs>g++ unapeared.c

D:\c_sources_bak\bbs>a
18 5
1 3 5 2 4 1 3 5 2 2 2 2 3 4 1 5 3 2
3

好强啊，呵呵 看了你代码才知道有这方法
只要判断出现几次1-P就可以，好想法啊 佩服