hdu6103Kirinriki(尺取法)

题意:给你一个上限距离m,和一行字符串。找两个不重叠的字符串(俩字符串长度相等),这两个字符串的距离小于m(距离的定义在题目中有解释)。求出最长的字符串,返回字符串(两个其中一个)的长度。

思路:枚举对称轴,从前端和后端都尺取一遍。

代码:

#include iostream
#include cstdio
#include cmath
#include cstring
#include set
#include algorithm

using namespace std;
const int maxn = 5000+10;
char str[maxn];

int main()
{
    int t;
    scanf("%d",t);
    while(t--)
    {
        int m;
        scanf("%d",m);
        scanf("%s",str);
        int len = strlen(str);
        int maxx = 0;
        for(int i = 2;i=len;i++)
        {
            int sum = 0,s = 0,e = 0;
            while(1)
            {
                while(ei/2sum=m)
                {
                    sum += abs(str[e]-str[i-1-e]);
                    e++;
                }
                if(e==i/2s==e)
                    break;
                if(sum=m)
                maxx = max(maxx,e-s);
                else
                    maxx = max(maxx,e-s-1);
                sum -= abs(str[s]-str[i-1-s]);
                s++;
            }
        }

        reverse(str,str+len);
        for(int i = 2;i=len;i++)
        {int sum = 0,s = 0,e = 0;
            while(1)
            {

            while(ei/2sum=m)
            {
                sum += abs(str[e]-str[i-1-e]);
                e++;
            }
            if(e==i/2s==e)
                break;
            if(sum=m)
                maxx = max(maxx,e-s);
                else
                    maxx = max(maxx,e-s-1);
            sum -= abs(str[s]-str[i-1-s]);
            s++;
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}

最新回复(0)
/jishuBdwxwAnCrNY2hb5eI4BT7i0RlDJqdOr1inf14aIbYaM_3D4794997
8 简首页