HDU 6740 MUV LUV EXTRA(求循环节)

发布时间:2022-04-30 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了HDU 6740 MUV LUV EXTRA(求循环节)脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6740

中文题意链接http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=872

 

题解:反向用next数组求循环节(前i个字符的)即可。注意ans初始化应该-inf(long long)

HDU 6740 MUV LUV EXTRA(求循环节)

#include <bITs/stdc++.h>

const int maxn=1e7+5;
int a,b;
char s[maxn],x[maxn];
int next[maxn];

void calnext(char x[],int m)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<m)
    {
        while(j!=-1 && x[i]!=x[j]) j=next[j];
        next[++i]=++j;
    }
}


int main()
{
    while(~scanf("%d%d%s",&amp;a,&b,s))
    {
        int cnt=0;
        for(int i=strlen(s)-1; i>=0; i--)
        {
            if(s[i]==.) break;
            x[cnt++]=s[i];
        }
        calnext(x,cnt);
        long long ans=-1e18;
        for(int i=1; i<=cnt; i++)
            ans=std::max(ans,1ll*a*i-1ll*b*(i-next[i]));
        PRintf("%lld\n",ans);
    }
    return 0;
}
View Code

脚本宝典总结

以上是脚本宝典为你收集整理的HDU 6740 MUV LUV EXTRA(求循环节)全部内容,希望文章能够帮你解决HDU 6740 MUV LUV EXTRA(求循环节)所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。