Array Painting

Created by LXC on Thu Mar 7 14:15:30 2024

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

ranting: 1700

tag: constructive algorithms, greedy, two pointers

problem

有一个长度为 $n$ 的数组 $a$，满足 $\forall a_i\in\lbrace 0,1,2\rbrace $，一开始所有元素均为蓝色。

可以有如下操作：

• 用一枚硬币，把一个蓝色元素涂成红色；

• 选择一个不等于 $0$ 的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少 $1$，并将所选的蓝色元素涂成红色。

要将所有元素涂红，最少需要多少硬币？

solution

对于连续非0的子段，我们可以压缩为当前段中的最大值，得到数组b。

例如给出a=[0,0,1,1,2,1,0,1,1,0,2,0],得到b=[0,0,2,0,1,0,2,0]

可见b数组中不存在两个相邻的非0数字。

我们可以用动态规划来做。定义$f_i$为前i个数涂为红色的最少次数。

当$b_{i-1} = 2$时，将$b_{i-1}$涂红，可以将$b_{i-2}, b_{i}$两个0变为红色，$f_{i} = f_{i-3}+1$

当$b_{i-1} = 1$时，将$b_{i-1}$涂红，可以将$b_{i}$的0变为红色，$f_{i} = f_{i-2}+1$

当$b_{i-1} = 0$时。若$b_{i} \ne 0$，可以将$b_{i}$涂红变为红色，并将$b_{i-1}$变为红色，$f_{i} = f_{i-2}+1$；否则只能单独将$b_{i}$涂红，$f_{i} = f_{i-1}+1$

code

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

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i:a) cin >> i;
    vector<int> b;
    for (int i=0,j; i<n; i=max(i+1, j)) {
        j = i;
        int mx = 0;
        while (j<n && a[j] != 0) mx = max(a[j], mx), j++;
        b.push_back(mx);
    }
    // cout << a << endl;
    // cout << b << endl;
    int sz = b.size();
    vector<int> f(sz, -1);
    function<int(int)> dfs = [&](int x) {
        if (x < 0) return 0;
        if (x == 0) return 1;
        if (f[x] != -1) return f[x];
        int res = dfs(x-1)+1;
        if (b[x-1] == 1) res = min(res, dfs(x-2)+1);
        if (b[x-1] == 2) res = min(res, dfs(x-3)+1);
        if (b[x-1] == 0) {
            if (b[x]) res = min(res, dfs(x-2)+1);
            else res = min(res, dfs(x-1)+1);
        }
        return f[x] = res;
    };
    cout << dfs(sz-1) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    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;
}