问题标题: 坏掉的项链[USACO 1.2] 两个点错了 不知道为何

1
1
已解决
束礼熙
束礼熙
初级守护
初级守护

 (不知道酷町堂题库有没有 所以我就把题目复制了一下)

坏掉的项链Broken Necklace[USACO 1.2]

题目描述

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

图A          图B

r 代表红色的珠子

b 代表蓝色的珠子

w 代表白色的珠子

 

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

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

brbrrrbbbrrrrrbrrbbrbbbbrrrrb

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

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

如图B所示,在一些项链中还存在白色的珠子,如果遇到白色珠子,白色珠子可以被当做红色也可以被当做蓝色。

写一个程序来确定项链从哪里打开,可以收集到的珠子数目最大。

输入格式

第 1 行: N, 项链中珠子的数目

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

输出格式

输出一行一个整数,表示从给出的项链中可以收集到的珠子的最大数量。

输入输出样列

输入样例1:

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出样例1:

11

【耗时限制】1000ms 【内存限制】128MB

我的代码:   ......

#include <bits/stdc++.h>
using namespace std;
int n,ans;
char a[8000];
int main()
{
    cin>>n;
    char c;
    for(int i=1;i<=n;i++)
    {
        cin>>c;
        a[i]=c;
        a[i+n]=c;        
    }
    for(int i=1;i<=n;i++)
    {
        int j=i,tot=0;
        char x=a[i];
        //左
        while(a[j]==x||a[j]=='w')
        {
            if(j==0)   
                j=n;
            tot++;
            j--;
        }
        x=a[i+1];
        j=i+1;
        //右
        while(a[j]==x||a[j]=='w')
        {
            j++;
            tot++;
        }
        if(tot>ans)
            ans=tot;
        if(ans>n)
        {
            cout<<n;
            exit(0);
        }
    }
    cout<<ans;
    return 0; 
}

 


0
0
0
我要回答