ACM模版

描述

题解

这个题要难为死我了，搞半天也不知道怎么做……

首先我们可以假设 A 一定在 B 左边，然后我们可以考虑 A 的尾部和 B 的起点，如果暂时不考虑长度不固定，我们每次查找都让长度尽可能长，那么，我们一定需要将 A 的尾部或者 B 的起点靠近，然后获取 A 向左延伸， B 向右延伸对应位置的贡献，然后呢？我们可以采用尺取法来进行 A 的尾部和 B 的起点向两侧的推移，当 dis2 大于 m 时，我们向两侧推移 A 的尾部和 B 的起点即可。在这个尺取法的过程中，记录下来最大的 dis 值即可。

简单的说就是，将整个区间划分为两份，然后左右各有一个序列，这个序列是贪心的，贪心的过程利用尺取法来维护最优解，而这里我们需要对区间的划分进行枚举，并且由于尺取法每次都是往左右各推移一位，所以我们需要考虑到中间是奇数个元素还是偶数个元素，所以此时的划分又要分为两种情况了。

也许我说的有些乱，结合代码看看吧，应该还是比较容易理解的了。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 5555;
const int MAXM = MAXN >> 1;

int n, m;
int cnt, ans;
int tmp[MAXM];
char s[MAXN];

void check()
{
    int dis = 0, dis2 = 0, x1 = 0, x2 = 0;
    while (x2 < cnt)
    {
        dis2 += tmp[x2++];
        while (dis2 > m)
        {
            dis2 -= tmp[x1++];
        }
        dis = max(dis, x2 - x1);
    }
    ans = max(ans, dis);
}

void solve()
{
    n = (int)strlen(s + 1);
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt = 0;
        int x1 = i - 1;
        int x2 = i + 1;
        while (x1 > 0 && x2 <= n)
        {
            tmp[cnt++] = abs(s[x1--] - s[x2++]);
        }
        check();
    }
    for (int i = 1; i <= n; i++)
    {
        cnt = 0;
        int x1 = i;
        int x2 = i + 1;
        while (x1 > 0 && x2 <= n)
        {
            tmp[cnt++] = abs(s[x1--] - s[x2++]);
        }
        check();
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%s",&m, s + 1);

        solve();

        printf("%d\n", ans);
    }

    return  0;
}