考场上写的贪心(骗得80分)：

#include<bits/stdc++.h>
using namespace std;
int n,d;
int h[5005],j[5005];
signed main(){
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>d;
	int H=0,J=0;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='H') H++;
		else J++;
		h[i]=H;j[i]=J;
	}
	int i=1,ans=0,ans2=0;
	while(i<=n){//important
		int k=n;
		for(;k>=1;k--){
			int J=j[k]-j[i-1],H=h[k]-h[i-1];
			if(!J||!H||abs(J-H)<=d){
				//特判全是一个球队的情况
				//因为要尽可能多的巴士
				ans++;
				break; 
			}
		}
		//cout<<i<<' '<<k<<endl;
		i=k+1;
	}
	cout<<ans;
	return 0;
}
/*
14 0
H 
J 
H 
H 
H 
J 
H 
J 
H 
H 
H 
H 
H 
H

5 2
H 
J 
H 
H 
H 

9 1
J
H
H
H
H
J
J
H
J

1

8 2
H J H H H J H H

8 2
H H J H H H J H

14 3 
H J H H H J H J H H H H H H

14 3
H H H H H H J H J H H H J H

21 0
H H H H J H J J J H J H H J J J H J H H J

7 1
H J J J H J J

2
*/

正解$DP$：

#include<bits/stdc++.h>
using namespace std;
int n,d;
int h[5005],j[5005];
int dp[5005];
signed main(){
	//freopen("ball.in","r",stdin);
	//freopen("ball.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>d;
	int H=0,J=0;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='H') H++;
		else J++;
		h[i]=H;j[i]=J;
		dp[i]=1e9;
	}
	for(int i=1;i<=n;i++){
		for(int k=i;k>=1;k--){
			int H=h[i]-h[k-1];
			int J=j[i]-j[k-1];
			if(abs(H-J)<=d||!H||!J){
				dp[i]=min(dp[i],dp[k-1]+1);
			}//这里应该好理解
		}
	}
	cout<<dp[n];
	return 0;
}
/*
14 0
H 
J 
H 
H 
H 
J 
H 
J 
H 
H 
H 
H 
H 
H

5 2
H 
J 
H 
H 
H 

9 1
J
H
H
H
H
J
J
H
J

1

8 2
H J H H H J H H

8 2
H H J H H H J H

14 3 
H J H H H J H J H H H H H H

14 3
H H H H H H J H J H H H J H

21 0
H H H H J H J J J H J H H J J J H J H H J

7 1
H J J J H J J

2
*/