牛客练习赛85考古 B (双指针预处理dp)

题目 题意: 给定长度为n的小写字母组成的字符串，要求找出三个彼此不相交的区间，使得三个区间的大小求和尽可能地大。要求每个区间中每种字母的数量不超过m. 思路: 如果是单个区间，直接双指针维护即可。但是现在是三个，其实有点套路了这个题。可以dp预处理1-i以及j-m的区间最大值，之后枚举中间的区间。 时间复杂度: O(n) 代码:

#include
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long ll;
const int N = 1e7+10;
int n,m,k,T;
int f[N]; //1-i的最大值
int g[N]; //i-n的最大值
char s[N];
int cnt[30];
int ans;
void solve()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    if(m > n)
    {
    	printf("%d\n",n);
    	return ;
    }
    mem(cnt,0);
    int l = 1;
    for(int r=1;rm) cnt[s[l++]-'a']--;
    	f[r] = max(f[r-1],r-l+1);
    }
    mem(cnt,0);
    l = n;
    for(int r=n;r>=1;--r)
    {
    	cnt[s[r]-'a']++;
    	while(cnt[s[r]-'a']>m) cnt[s[l--]-'a']--;
    	g[r] = max(g[r+1],l-r+1);
    }
    mem(cnt,0);
    l = 1;
    for(int r=1;rm&&l