【USACO题库】1.1.4 Broken Necklace破碎的项链

    xiaoxiao2025-07-21  8

    题目描述 你有一条由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]))

    转载请注明原文地址: https://ju.6miu.com/read-1300924.html
    最新回复(0)