牛客wannafly挑战赛12 C-删除子串(DP)

链接：https://www.nowcoder.com/acm/contest/79/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给你一个长度为n且由a和b组成的字符串，你可以删除其中任意的部分（可以不删），使得删除后的子串“变化”次数小于等于m次且最长。
变化：如果a[i]!=a[i+1]则为一次变化。（且新的字符串的首字母必须是'a'）
如果初始串全为b，则输出0。

输入描述:

第一行输入两个数n,m。（1 <= n <= 10⁵,0 <= m <= 10）

第二行输入一行长度为n且由a和b组成的字符串

输出描述:

输出一个数字表示最长长度

示例1

输入

8 2
aabbabab

输出

6

说明

原串可以变成aabbbb，只改变了一次，且长度最长。


分析：动态规划。a[i]表示以a结尾的子串,变化数为i的时候,子串的最长长度，
b[i]表示以b结尾的子串,变化数为i的时候,子串的最长长度，
把s串扫一次，那么,当s[k]=='a'的时候,a[i]=max(a[i],b[i-1])+1;
当s[k]=='b'的时候,b[i]=max(b[i],a[i-1])+1;
开头必须是a，初始化b[0]=0.

#include<cstdio>
#include<algorithm>
using namespace std;
char s[100100];
int a[13],b[13];
int main()
{
    int N,M;
    scanf("%d%d%s",&N,&M,s);
    int k=0;
    while(s[k]=='b') k++;
    for(;k<N;k++)
    {
        if(s[k]=='a') a[0]++;
        for(int i=1;i<=M;i++)
            if(s[k]=='a')
                a[i]=max(a[i],b[i-1])+1;
            else
                b[i]=max(b[i],a[i-1])+1;
    }
    int ans=0;
    for(int i=0;i<=M;i++)
    ans=max(ans,max(a[i],b[i]));
    printf("%d
",ans);
    return 0;
}