Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- #define ll long long
- #define cy cout << "YES"
- #define cn cout << "NO"
- #define nl "\n"
- #define fi first
- #define se second
- #define cin(v) for (int i = 0; i < n, cin >> v[i]; i++)
- #define cout(v) for (int i = 0; i < v.size(), cout << v[i] << " "; i++)
- #define all(v) v.begin(), v.end()
- #define sz(s) s.size()
- void sherry()
- {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- ll n;
- vector<ll> a;
- vector<vector<int>> dp;
- int rec(int idx, int prev)
- {
- if (idx == n)
- return 0;
- int &ret = dp[idx][prev];
- if (~ret)
- return ret;
- ret = 1e9;
- if (a[idx] == 0)
- return ret = 1 + rec(idx + 1, a[idx]);
- if (a[idx] == 1 || a[idx] == 2)
- return ret = (a[idx] == prev) + rec(idx + 1, (a[idx] == prev ? 0 : a[idx]));
- if (a[idx] == 3)
- {
- if (prev == 1)
- ret = min(ret, rec(idx + 1, 2));
- else if (prev == 2)
- ret = min(ret, rec(idx + 1, 1));
- else
- ret = min({ret, rec(idx + 1, 1), rec(idx + 1, 2)});
- }
- return ret;
- }
- void solve()
- {
- cin >> n;
- a.resize(n);
- cin(a);
- dp.assign(n, vector<int>(4, -1));
- cout << rec(0, 0);
- }
- int main()
- {
- sherry();
- int t = 1;
- // cin >> t;
- while (t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement