HDU 6103 Kirinriki(尺取法)

先暴力,因为这题大致就相当于取最长对称串,这个对称串只要满足题目的d

#includebits/stdc++.h
using namespace std;

int t,m;
int dp[10100];
char str[10050];

int main()
{
    scanf("%d",t);
    while(t--)
    {
        scanf("%d",m);
        scanf("%s",str);
        int len = strlen(str);
        int ans=0;
        int laz=0;
        for(int i=0;i2*len-1;i++)//表示对称点,因为对称部分可以在两个字符之间的留白部分,所以循环两倍len,一定不要像manacher那样子加字符找,时间多四倍肯定不够。会TLE。
        {
            int sum=0;int num=0;
            memset(dp,0,sizeof(dp));
            if(i%2)
            {
                int ibegin=i/2;
                int iend = i/2+1;
                while(ibegin=0iendlen)
                {
                    dp[i/2-ibegin+1] = abs((int)(str[ibegin]-str[iend]));
                    ibegin--;iend++;
                }
                int t=1;int s=1;
                for(;;)//尺取
                {
                    while(t=i/2-ibeginsum=m)
                    {
                        sum+=dp[t++];
                    }
                    if(summ)
                        ans=max(t-s-1,ans);
                    else ans=max(ans,t-s);
                    if(summ) break;
                    sum-=dp[s++];
                }
            }
            else
            {
                int ibegin=i/2-1;
                int iend = i/2+1;
                while(ibegin=0iendlen)
                {
                    dp[i/2-ibegin] = abs((int)(str[ibegin]-str[iend]));
                    ibegin--;iend++;
                }
                int t=1;int s=1;
                for(;;)
                {
                    while(t=i/2-1-ibeginsum=m)
                    {
                        sum+=dp[t++];
                    }
                    if(summ)
                        ans=max(t-s-1,ans);
                    else ans=max(ans,t-s);
                    if(summ) break;
                    sum-=dp[s++];
                }
            }
        }
        printf("%d\n",ans);
    }
}
最新回复(0)
/jishuwo1D8_2F7ipEZ5NOV_2Br_2BktSfTKi_2FYCM6VC_2BTUCEbxwjHU_3D4794992
8 简首页