【链接】http://acm.hdu.edu.cn/showproblem.php?pid=6103

【题意】

给出一串字符串，从中选出两个不重叠的字符串，使得两个字符串的距离和 <= m 的最长字符串长度，A,B 串中的字符距离计算为 disA,B=∑i=0n−1|Ai−Bn−1−i|

【题解】

两个不相交的串s1和s2,它们之间必然有一个中心点,则我们可以枚举每一个中心点,然后往两边扩展这两个字符串.

这样有什么好处呢?

就是在扩展的时候,如果发现这个时候两个字符串的差值大于m了,则可以把第一次得到的差值减掉,然后再尝试扩展;

表示删掉左边那个串的最后一个字符,和右边那个串的第一个字符.

然后剩下的字符之差也是符合定义的差值了.

但是中心点可能不是一个点,可能在两个点之间.所以还得考虑中心点在两个点之间的情况.

在扩展的时候更新最大值即可.

【错的次数】

0

【反思】

在这了写反思

【代码】

#include
#define ll long long
using namespace std;
const int MAXN = 5000+100;
const int MO = 1e9+7;
char ar[MAXN];
int m,len;
int ans;
int ww[MAXN];
void f(int st,int en)
{
int tem=0;
int stt=0,enn=0;
while(st>=0&&enm&&enn-stt>0)
{
tem-=ww[stt];
stt++;
}
st--;en++;
if(tem<=m)
ans=max(ans,enn-stt);
else
tem=0;
}
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
scanf("%s",ar);
ans=0;
len = strlen(ar);
for(int i=0;i<len;i++)
{
f(i-1,i+1);
f(i,i+1);
}
printf("%d\n",ans);
}
return 0;

}