C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2018-10-23 22:39:00

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int a[13],b[13];
char s[1000005];
int main() {
	int n,m;
	scanf("%d %d %s",&n,&m,s + 1);
	int k = 1;
	while(k <= n && s[k] == 'b') k++;
	rep(i,k,n) {
		a[0] += (s[i] == 'a');
		rep(j,1,m) {
			if(s[i] == 'a') {
				a[j] = max(a[j],b[j-1]) + 1;
			} else {
				b[j] = max(b[j],a[j-1]) + 1;
			}
		}
	}
	int ans = 0;
	rep(i,1,m) {
		ans = max(ans,max(a[i],b[i]));
	}
	cout << ans;
}

C++ 解法, 执行用时: 7ms, 内存消耗: 556K, 提交时间: 2021-11-10 20:25:49

#include<bits/stdc++.h>
using namespace std;
string s;
int a[15],b[15],n,m,cnt,ans;
int main()
{
	cin>>n>>m>>s;
	while(s[cnt]=='b') cnt++;
	for(;cnt<n;cnt++)
	{
		if(s[cnt]=='a') a[0]++;
		for(int i=1;i<=m;i++)
        {
            if(s[cnt]=='a') a[i]=max(a[i],b[i-1])+1;
			else b[i]=max(b[i],a[i-1])+1;
        }
	}
	for(int i=0;i<=m;i++) ans=max(ans,max(a[i],b[i]));
	cout<<ans;
	return 0;
}