A20228. 博弈游戏
填空题
困难
知识点
题目描述
博弈游戏
题目描述
两位玩家进行回合制博弈游戏，游戏总计进行 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≤200000，si∈{1,2,3}
限制
时间限制：1000ms，内存限制：256MiB
参考答案
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
int ans = 0;
int last = 0; // 上一轮出的数
for (int x : s) {
int win; // 能赢的数
int draw = x; // 能平的数
// 计算克制关系：1克2，2克3，3克1
if (x == 1) win = 3;
else if (x == 2) win = 1;
else win = 2;
// 优先选赢的，只要不和上一轮重复
if (win != last) {
ans++;
last = win;
}
// 不能赢 → 只能平
else {
last = draw;
}
}
cout << ans << endl;
return 0;
}
上一题
下一题