记录编号	163291	评测结果	AAAAAAAAAA
题目名称	看球的巴士	最终得分	100
用户昵称	OI88	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2015-05-23 20:04:13	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#define min(a,b) (a)<(b)?(a):(b)
#define INF 0x3fffffff
#define abs(x) ((x)>0?(x):(-(x)))
using namespace std;
int n,d,j,h,f[2502],q[2502],jsimilar[2502],hsimilar[2502];
int main()
{
	ios::sync_with_stdio(false);
	freopen("iinput.in","r",stdin);
	freopen("iinput.out","w",stdout);
	cin>>n>>d; 					//readin
	for(int i=1;i<=n;i++)
	{
		char x;
		cin>>x;
		if(x=='H')
		{
			q[i]=1;
			h++;
		}
		else
		{
			q[i]=2;       //symbolize
			j++;
		}
		jsimilar[i]=j;    //jsimilar(第i个位置j相同的数目)
		hsimilar[i]=h;   //hsimilar（第i个位置h相同的数目）
		f[i]=INF;		//初始化
	}
	f[1]=1;
	f[0]=0;				//初始化
	for(int i=1;i<=n;i++)
	{
		for(int o=1;o<=i-1;o++)
			if(jsimilar[i]-jsimilar[o-1]==0  ||  hsimilar[i]-hsimilar[o-1]==0  ||  abs(jsimilar[i]-jsimilar[o-1]-hsimilar[i]+hsimilar[o-1])<=d )
				f[i]=min(f[i],f[o-1]+1);//因为有可能一辆车都是一队人
		f[i]=min(f[i-1]+1,f[i]);		//巴士的辆数更新
	}
	cout<<f[n];
}