#CW23. 红色(red)
红色(red)
题目描述
有一个长度为 的数组。一个位置最多会有红、绿、蓝三种颜色,最少会有一种颜色。
第 个位置由三个整数 描述,分别表示该位置是否具有红、绿、蓝这三种颜色。
对于一个连续区间 ,定义其中三种颜色的数量:
$$R=\sum_{i=l}^{r}a_i,\quad G=\sum_{i=l}^{r}b_i,\quad B=\sum_{i=l}^{r}c_i.$$若满足 且 ,则称区间 为红色区间。
现在请将整个数组划分为若干个非空连续区间。
一次划分的得分为:所有被划分出的红色区间的长度之和。
注意,非红色区间的长度不计入得分,但它仍然可以是划分的一部分。
求所有划分方案中的最大得分。
输入格式
第一行包含一个整数 。
接下来 行,每行包含三个整数 ,表示第 个位置的三种颜色信息。
输出格式
输出一个整数,表示最大得分。
样例 1 输入
6
0 1 0
0 0 1
1 0 1
1 0 0
0 1 0
0 0 1
样例 1 输出
5
样例 1 解释
可以将前五个位置划为一个区间、最后一个位置单独划为一个区间。
数据范围
对于所有测试数据,保证:,,。
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
| 无 | ||