Omkar and Bed Wars

Created by LXC on Fri May 5 13:38:57 2023

https://codeforces.com/problemset/problem/1392/D

ranting: 1700

tag: dp, greedy

题意

给出n个人排列成环

每个人可以攻击相邻左边或者右边的人。

攻击的游戏规则是如果一个人只被一个人攻击那么，就需要反击。
否则任意攻击相邻的人之一。

现在给出这n个人的攻击方向（左或者右），你可以说服任何人改变攻击方向，问最少需要说服多少人使得攻击满足游戏规则。

题解

如果用动态规划状态复杂。

考虑贪心。我们需要找出一些性质。

观察后发现不能有连续三个人的攻击方向一致

因此统计每个攻击方向一致的连续段$s_i$，答案便为$\sum \lfloor \frac{s_i}{3} \rfloor$

注意如果所有人的攻击方向一致，那么答案特殊情况$\lceil \frac{n}{3} \rceil$

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    string s;
    cin >> n >> s;
    int cr = count(s.begin(), s.end(), 'R');
    if (cr == 0 || cr == n) {
        cout << (n + 2) / 3 << "\n";
    } else {
        while (s.size() && s.back() == s[0])
            s.pop_back();
        s = string(n - s.size(), s[0]) + s;
        int ans = 0, p = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != s[p]) {
                ans += (i - p) / 3;
                p = i;
            }
        }
        ans += (n - p) / 3;
        cout << ans << "\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}