HDU6103---Kirinriki（2017多校联赛：滑动窗）

本文主要是介绍HDU6103---Kirinriki（2017多校联赛：滑动窗），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：http://acm.hdu.edu.cn/php?pid=6103

题意

给出一个字符串，从中分离出尽量长两个子串（不想交）使得他们的dis（按照体面描述的）不大于m，输出长度（两个子串长度一致）。

思路

按照题意，先用总字符串和它本身反过来之后的进行dis运算，得出一个表，根据这个表，利用去枚举所有可能情况。
这里写图片描述（有点乱。。。）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[5000+10];
int m,ans,len;
void init()
{scanf("%d",&m);getchar();gets(s);ans=0;len=strlen(s);
}
void solve(int x)
{int k=1,limit=len/2,numRes=len;while(1){if(ans>=limit||k==len+1)break;int nowM=0,nowLength=0,stI=0,stJ=len-k,j=len-k,i=0;//双指针进行维护for(; j>=0&&i<limit; j--,i++){nowM+=abs(s[i]-s[j]);nowLength++;while(nowM>m)//若超出m，那就把前面的去掉{nowM-=abs(s[stI]-s[stJ]);stI++;stJ--;nowLength--;}if(nowLength>ans)ans=nowLength;}numRes--;limit=numRes/2;//取半就可以，因为为了避免重复计算k++;}if(!x)//反着再来一次for(int i=0;i<len/2;i++)swap(s[i],s[len-i-1]);elseprintf("%d\n",ans);
}
int main()
{int T;scanf("%d",&T);while(T--){init();solve(0);solve(1);}
}