3377: [Usaco2004 Open]The Cow Lineup 奶牛序列

3377: [Usaco2004 Open]The Cow Lineup 奶牛序列

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 16  Solved: 11

[Submit][Status][Discuss]

Description

    约翰的N(1≤N≤100000)只奶牛站成了一列.每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在1…K(1≤K≤10000)范围内.比如有这样一个队列

    1,5,3,2,5,3,4,4,2,5,1,2,3

根据约翰敏锐的数学神经,他发现一些子序列在这个队列里出现,比如3,4,1,3,而另一些没有.子序列的各项之间穿插有其他数,也可认为这个子序列存在, 现在,他想找出一个最短的子序列(由1..K组成),使之不在奶牛序列里出现.达个子序列的长度是多少呢?

Input

    第1行输入两个整数N和K,接下来N行输入奶牛序列.

Output

    最短的不出现子序列.

Sample Input

14 5 1 5 3 2 5 1 3 4 4 2 5 1 2 3

Sample Output

3 样例说明 所有的长度为1和为2的子序列都出现.长度为3的序列“2,2,4”不出现

HINT

Source

Green

题解:这是一道很神的乱搞题。。。居然结果弄来弄去是完全连续块的个数+1

(完全连续块表示连续的某一段包含了所有的数字,比如样例(1,5,3,2,5,1,3,4),(4,2,5,1,2,3)可以分成两块,所以答案是2+1=3)

 1 /**************************************************************
 2     Problem: 3377
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:84 ms
 7     Memory:304 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12    a:array[0..20000] of longint;
13 begin
14      readln(n,m);l:=0;k:=1;
15      for i:=1 to n do
16          begin
17               readln(j);
18               l:=l+k-a[j];
19               a[j]:=k;
20               if l=m then
21                  begin
22                       inc(k);
23                       l:=0;
24                  end;
25          end;
26      writeln(k);
27      readln;
28 end.          

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

图的着色

图着色问题,相邻的点颜色不同       基础知识:http://wenku.baidu.com/view/d7242fd1c1c708a1284a444d.h...

2827
来自专栏ml

HDUOJ-----Be the Winner

1 此题用到的概念: 【定义1】:若一堆中仅有一个石子,则被称为孤单堆。若大于1个,则称为充裕堆。 【定义2】:T态中,若充裕堆的堆数大于等于2,则称为完全利他...

2728
来自专栏开发 & 算法杂谈

凸包问题之蛮力解法

1  点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1...

1172
来自专栏简书专栏

基于Excel2013的文本函数

CONCATENATE函数既能引用一个区域直接合并,又不会漏掉数值、日期和公式结果,还能引用多个区域,比&符号更好用。

1074
来自专栏算法修养

HOJ-2056 Bookshelf(线性动态规划)

L is a rather sluttish guy. He almost never clean up his surroundings or regulat...

3377
来自专栏算法修养

POJ-2346 Lucky tickets(线性DP)

Lucky tickets Time Limit: 1000MS Memory Limit: 65536K Total Submissions...

2497
来自专栏来自地球男人的部落格

[LeetCode] 74. Search a 2D Matrix

【原题】 Write an efficient algorithm that searches for a value in an m x n matrix. ...

1968
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

38112
来自专栏desperate633

[编程题] 彩色瓷砖分析代码

牛牛喜欢彩色的东西,尤其是彩色的瓷砖。牛牛的房间内铺有L块正方形瓷砖。每块砖的颜色有四种可能:红、绿、蓝、黄。给定一个字符串S, 如果S的第i个字符是'R', ...

923
来自专栏懒人开发

(8.1)James Stewart Calculus 5th Edition:Arc Length

半立方抛物线?? 这名词.... 也就是求一个函数,2个点之间的弧长 这2个点,我们知道对应的x取值范围 可以得到对应的表达式为

862

扫码关注云+社区

领取腾讯云代金券