PKU 1989 The Cow Lineup
http://poj.org/problem?id=1989
k種類の数字からなる長さnの数列がある。
この数列から部分列を作る。
この時に、この数列からある部分列を作れなくなるような最小の部分列の長さを答えろというような問題。
かなり前からずっと考えていてやっと解き方が分かりました。
頭がもう少しやわかければいいんですけどね。
k種類全ての数字が出現するまとまりを前から順番に数えていくような感じです。
bool app[10000]; main(){ int n,k; scanf("%d%d",&n,&k); int ans=0; int num=0; rep(i,n){ int t; scanf("%d",&t); --t; if(app[t])continue; app[t]=true; ++num; if(num==k){ num=0; ++ans; memset(app,0,sizeof(app)); } } cout<<ans+1<<endl; }