F. New Year and Rainbow Roads

GoodBye2017 F题。

最后一分钟被绝杀,被手速坑了。。。

容易发现,R,B都必须与G相连,分下面三种情况

1.对于在最左边G的左边的点,一定会连这个G

2.那么也就是在某两个G中间,求得如何连接使得两个黑点(经过R,B )花费最小

3.对于在最右边G的右边的点,一定会连这个G

1 3 很简单,考虑2,有下面几种情况:

1.两个G中间没有RB,那么连接两个G就好了。

2.两个G中间有R,那么必须连接两个G,然后把R分为两段,左边的一段与左边的G相连,右边的一段与右边的G相连。

3.两个G中间有B,与2同理

4.两个G中间有B R,那么可以把 区间里的B和R分别串在一起,再与G相连,或者像上面那样找出分割点,然后分别与G相连,那么求得这两个值得最小值就好了。

另外 ,还要特判没有G得情况,直接就是RB得链长和

c++代码如下:

 

 

 

 

1 + 2 =