记录编号	309498	评测结果	AAAAAAAAAA
题目名称	看球的巴士	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2016-09-19 20:55:22	内存使用	0.36 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=4000;
int f[maxn],a[maxn],b[maxn],n,m;
char h[2];
int main()
{
    freopen("iinput.in","r",stdin);
    freopen("iinput.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",h);
        if(h[0]=='H') a[i]=1;else a[i]=2;
        if(a[i]==2) a[i]=0,b[i]=1;
        else b[i]=0;

    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;f[1]=1;
    for(int i=1;i<=n;i++) a[i]+=a[i-1],b[i]+=b[i-1];
    for(int i=1;i<=n;i++)
    {
        int ans=10100107;
        for(int j=1;j<=i;j++)
        {
            int x=a[i]-a[j-1],y=b[i]-b[j-1];
			if(x==0||y==0||abs(x-y)<=m)
			{
                ans=min(ans,f[j-1]+1);
			}
        }
        f[i]=ans;
    }
    printf("%d",f[n]);
    return 0;
}