->  Link  <-

题目就不贴出来了，链接在上面；

题意：给定n,k,然后是一个长度为n的只含字母a、b的字符串，问至多改变k次使得一个子串字母都相同且长度最大，如所给样例：

10 1

bbabbabbba

6

这个字符串很明显将第二个a改为b，所以字串中字母相同且长度最大的就是6了；

那么怎么解决这个问题呢，①按照我们的思路当然是先找一个包含一种字母个数最多的字串，字串中另一种字母的个数不超过k，所以可以按这个思路去找；这是从个数多的字母出发，②那么我们也可以从个数少的字母出发，找一个字母个数不超过k的区间使其长度最大； 明白了吗，找k个是因为要改变k次，另一种不用变，我们只需找出符合条件且长度最大就行；

来看第二种思路代码：

const int N=100000+10;

int va[N],vb[N];//区间a、b的个数；

char a[N];

int main()

{

    int n,k,i;

    while(~scanf("%d%d",&n,&k))

    {

       memset(va,0,sizeof(va));

       memset(vb,0,sizeof(vb));

       scanf("%s",a);

       for(i=0;i<n;i++)

       {

           if(a[i]=='a')

            va[i]=va[i-1]+1,

            vb[i]=vb[i-1];//将整个区间一种字母累加，方便求一个区间的这种字母个数；

            else

            vb[i]=vb[i-1]+1,

            va[i]=va[i-1];

       }

       int max1=0,max2=0,j=0;

       for(i=0;i<n;i++)//假设a为最长的；

       {

           while(vb[i]-vb[j-1]>k)//这时就需要改变b了，所以求一个区间b的个数不超过k;

           {

               j++;//当b的个数不超过k时区间长度就是i-j+1;

           }

           max1=max(max1,i-j+1);

       }

       j=0;//下面同上；

       for(i=0;i<n;i++)//假设b为最长的；

       {

           while(va[i]-va[j-1]>k)//区间内a的个数不超过k;

           {

               j++;

           }

           max2=max(max2,i-j+1);

       }

       printf("%d\n",max(max1,max2));//再求出最长的字串；

    }

    return 0;

}

这种区间dp问题CF已经考过好几次了，上次有个题也是用的这种方法做出来的，所以感觉一种问题有好的思路就可以发散性的解决其他问题；