PKU 1989-The Cow Lineup

問題概要

1〜Kの数字を含んだN項の数列が与えられる．数列の部分列とならないような最小の部分列の長さを求めてください．

解法

「数列を先頭から見ていき，K種類の数字のうち一番最後に表われるものを使い，それまでの数字を消す」ということを繰り返す貪欲法で形成出来ます．

実装(C++)

#include <cstdio>
#include <cstring>
using namespace std;
bool used[10000];
int a,N,K,ans,cnt;
int main() {
	scanf("%d%d",&N,&K);
	for(int i=0;i<N;i++){
		scanf("%d",&a);
		a--;
		if(used[a]==false){
			used[a]=true;
			cnt++;
		}
		if(cnt==K){
			memset(used,0,sizeof(used));
			cnt=0;ans++;
		}
	}
	printf("%d\n",ans+1);
	return 0;
}