冒险公社

 

https://ac.nowcoder.com/acm/contest/23106/K

题意

​ 我们得到一个数组,该数组的第 i 位表示从该位起,往前三位的颜色中红色和绿色那种更多,若相等则为黑色。我们需要求出来最终绿色数量最多的一种情况。 ​

思路

​ 我们可以发现,如果我们确定其中三座岛屿的话,那么我们便可以准确推断出来我们的最后一位的岛屿的颜色是怎么样的,如果我们这些岛屿颜色正确的话,那么我们寻找其前几位的颜色即可。 ​ 因此我们定义这样的状态 f[n][i][j][k] 表示目前在第 n 座岛屿上,并且第 n位的颜色为in-1 位的颜色为 j , n - 2 位的颜色位 k 时绿色最多时候的情况,那么我们就可以得到这样的方程了。 ​ \(f[n][i][j][k] = max(f[n-1][j][k][l] + [i = -1])\) ​

我选择使用 -1 作为 ‘R’ , 0 作为’B’,1 作为’R’

code

algorithm