记录编号	162217	评测结果	AAAAAAAAAA
题目名称	看球的巴士	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2015-05-15 14:00:02	内存使用	0.31 MiB

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int n,d,f[3001],a[3001]= {0};
char s[3001];
int min(int a,int b) {
	return a<b?a:b;
}
int main() {
	freopen("iinput.in","r",stdin);
	freopen("iinput.out","w",stdout);
	for(int i=0; i<=2800; i++) f[i]=0x7FFFFF;
	scanf("%d%d\n",&n,&d);
	for(int i=1; i<=n; i++) {
		s[i]=getchar();
		getchar();
		if(s[i]=='H') a[i]=a[i-1]+1;
		else a[i]=a[i-1]-1;
	}
	f[0]=0;
	for(int i=0; i<=n-1; i++) {
		for(int j=i+1; j<=n; j++)
			if(abs(a[i]-a[j])==j-i || abs(a[i]-a[j])<=d)
				if(f[i]+1<f[j] ) f[j]=f[i]+1;
	}
	printf("%d\n",f[n]);
}