题目描述 你有一条由N个红色的,白色的,或蓝色的珠子组成的项链(3<=N<=35000),珠子是随意安排的。 这里是 n=29 的二个例子: 1 2 1 2 r b b r b r r b r b b b r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w 图片 A 图片 B r 代表 红色的珠子 b 代表 蓝色的珠子 w 代表 白色的珠子 第一和第二个珠子在图片中已经被作记号。 图片 A 中的项链可以用下面的字符串表示: brbrrrbbbrrrrrbrrbbrbbbbrrrrb . 假如你要在一些点打破项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子,在另一端做同样的事。(颜色可能与在这之前收集的不同) 确定应该在哪里打破项链来收集到最大多数的数目的子。 Example 举例来说,在图片 A 中的项链,可以收集到8个珠子,在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链。 在一些项链中,包括白色的珠子如图片 B 所示。 当收集珠子的时候,一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。 表现项链的字符串将会包括三符号 r , b 和 w 。 写一个程序来确定从一条被供应的项链最大可以被收集珠子数目。 输入 第 1 行: N, 珠子的数目 第 2 行: 一串度为N的字符串, 每个字符是 r , b 或 w。 输出 单独的一行包含从被供应的项链可以被收集的珠子数目的最大值。 样例输入 29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb 样例输出 11
这道题第一次做时用的是暴力,后来装逼改成了前缀和
我们先建4个数组
R1[i]表示从第1个位置到第i个位置红白珠的数量
R2[i]表示从第i个位置到第n个位置红白珠的数量
B1[i]表示从第1个位置到第i个位置蓝白珠的数量
B2[i]表示从第i个位置到第n个位置蓝白珠的数量 因为白珠可以被当成红珠和蓝珠使用,所以我们在统计珠子的数量是要把白珠也加进去。
处理完之后,就可以开始我们伟(wei)大(suo)的前缀和
我们只要枚举断开的位置,再计算左右两边红蓝珠的最大值之和,要注意是从两个珠子之间断开,所以左边是i,右边是i+1。
一重循环枚举i,最终答案就是max(max(r1[i],b1[i])+max(r2[i+1],b2[i+1]))