博弈游戏

博弈游戏 题目描述 两位玩家进行回合制博弈游戏，游戏总计进行 n 轮。每一轮，双方都要从1、2、3三个数字中选择一个出招，胜负规则如下： （1）若双方选择的数字相同，本轮为平局； （2）若数字不同，胜负遵循固定克制关系：1克制2，2克制3，3克制1，被克制的一方本轮落败，克制的一方本轮获胜。 其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si，所有 si 组成一个长度为 n 的序列。 该玩家需要规划自己每一轮的出招，满足以下全部条件： （1）任何一轮都不能落败（即每一轮只能获胜或平局）； （2）不能连续两轮选择相同的数字出招； （3）在满足前两个条件的前提下，尽可能多地获得轮次的胜利。 请计算该玩家最多能赢得的轮次数量。 输入格式 第一行：一个整数表示n。 第二行：n 个整数，表示s1、s2、……、sn，每个数为1、2或3。 输出格式 输出一个整数，表示玩家最多能赢得的游戏轮数。 输入样例#1

6
3 1 2 2 1 2

输出样例#1

5

输入样例#2

24
2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2

输出样例#2

18

说明提示： 1≤n≤200,000，si∈{1,2,3} 限制： 时间限制：1000ms，内存限制：256MiB