洛谷P1203 坏掉的项链

首先看到这题的数据样例，3<=n<=350，不是水水暴搜就过了嘛

不难想到暴力解，先破环成链

因为可能有全部都可换成一种颜色的情况，考虑每次遇到s[i]==s[i+1]的情况，直接跳过，

如果最后结局ans仍为初始值（推荐-1），直接输出项链大小n，否则判断当前节点是否为white，如果是white就赋值一种颜色，左右暴搜，如果暴搜过程中发现得到的值比n还要大，直接返回n，然后赋值另一种继续搜，每次ans=max{ans, check(i)}，最后赋值回white，然后就A了，很水的题对吧

下面贴一下核心代码

int check(int x){

    int ans=0;

    char c2 = a[x+1],c1=a[x];

    for(int i=x;;i--){

        if(a[i]==c1)ans++;

        else if(a[i]=='w')ans++;

        else break;

        if(ans >= n)return n;

    }

    for(int i=x+1;;i++){

        if(a[i]==c2)ans++;

        else if(a[i]=='w')ans++;

        else break;

        if(ans >= n)return n;

    }

    return ans;

}

真的，好困，，好困(ﾟДﾟ≡ﾟДﾟ)谁在说话？

巴特西

洛谷P1203 坏掉的项链

最新文章

热门文章