USACO 2004 Open The Cow Lineupoj25965

题目大意：

输入n k，n头牛 k个品种

接下来n行描述每头牛的品种

输出无法找出的最短子序列的长度

Sample Input

14 515325134425123

Sample Output

3

Hint

All the single digit 'sequences' appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear.

  开始一直不理解题意  其实需要注意的是 如 11  22  33 或是 254 111 这类都属于其子序列  其实这个子序列不需要有序 就是任意组合 想明白这个就懂了   解题思路来自 http://blog.csdn.net/thinfatty/article/details/75949410 考虑长度为2的排列的情况，我们知道， 假如说在a~b的位置出现了1~k（可以多次出现）， 而在c~d的位置也出现了1~k（可以多次出现）， 其中a<b<c<d， 那么必定2的排列都齐了。两两配对嘛。 所以一个长度为len的排列全部到齐的条件是， 存在len个不交叉的1~k的段， 不交叉的意思就是没有相同覆盖的地方。   比如说 123 在132123213中能找到不重复的三段123 即 132 123 213 那么123所有的长度为3的任意组合都能在序列中找到 #include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int main(){ int n,k; while(~scanf("%d%d",&n,&k)) { int ans=1,flag[10005],tmp,t=0; memset(flag,INF,sizeof(flag)); while(n--) { scanf("%d",&tmp); if(flag[tmp]!=ans) { flag[tmp]=ans; if(++t==k) ans++,t=0; //printf("tmp:%d flag[tmp]:%d ans:%d\n",tmp,flag[tmp],ans); } } printf("%d\n",ans); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8583165.html