P1203 [USACO1.1]坏掉的项链Broken Necklace

题目描述

你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。这里是 n=29 的二个例子:

第一和第二个珠子在图片中已经被作记号。

图片 A 中的项链可以用下面的字符串表示：

brbrrrbbbrrrrrbrrbbrbbbbrrrrb

假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。确定应该在哪里打破项链来收集到最大数目的珠子。

例如，在图片 A 中的项链中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链可以收集到8个珠子。

白色珠子什么意思?

在一些项链中还包括白色的珠子(如图片B) 所示。

当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。

表现含有白珠项链的字符串将会包括三个符号 r ， b 和 w 。

写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。

输入输出格式

输入格式：

第 1 行: N, 珠子的数目

第 2 行: 一串长度为N的字符串, 每个字符是 r ， b 或 w。

输出格式：

输入输出样例

输入样例#1：

29

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出样例#1：

说明

题目翻译来自NOCOW。

USACO Training Section 1.1

代码很烂、、

这个题目有一个深渊巨坑：有可能整条串都是一样的！！！所以最后要特判

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

const int MAXN = 350 + 20;

const int INF = 9999999;

int n;

char s[MAXN * 2];

int pre[MAXN];

int next[MAXN];

int max;

int main()

{

    scanf("%d", &n);

    scanf("%s", s + 1);

    for(int i = n + 1;i <= n + n -1;i ++)

    {

        s[i] = s[i - n];

    }

    int temp = n + n -1;

    pre[1] = 1;

    for(int i = 2;i <= temp; i ++)

    {

        if(s[i] == s[i - 1] || s[i] == 'w')

        {

            pre[i] = pre[i - 1] + 1;

        }

        else

        {

            int a = i - 1;

            if(s[i - 1] == 'w')

            {

                while(s[a] == 'w' && s[a])

                {

                    a --;

                }

                if(s[i] == s[a])

                {

                    pre[i] = pre[i - 1] + 1;

                }

                else

                {

                    pre[i] = 2;

                }

                continue;

            }

            pre[i] = 1;

        }

    }

    next[temp] = 1;

    for(int i = temp - 1;i >= 1; i --)

    {

        if(s[i] == s[i + 1] || s[i] == 'w')

        {

            next[i] = next[i + 1] + 1;

        }

        else

        {

            int a = i + 1;

            if(s[i + 1] == 'w')

            {

                while(s[a] == 'w' && s[a])

                {

                    a ++;

                }

                if(s[i] == s[a])

                {

                    next[i] = next[i + 1] + 1;

                }

                else

                {

                    next[i] = 2;

                }

                continue;

            }

            next[i] = 1;

        }

    }

    bool ok =true;

    for (int i = 1; i <= n + n - 1; i ++)

    {

        max = std::max(max, pre[i - 1] + next[i]);

    }

    if(max > n) max = n;

    printf("%d", max);

    return 0;

}

巴特西

【P1203】【USACO1.1】坏掉的项链Broken Necklace

P1203 [USACO1.1]坏掉的项链Broken Necklace

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

【P1203】 【USACO1.1】坏掉的项链Broken Necklace

P1203 [USACO1.1]坏掉的项链Broken Necklace

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

【P1203】【USACO1.1】坏掉的项链Broken Necklace