Advertisement
sherry_ahmos

vacations

Nov 30th, 2022
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define cy cout << "YES"
  9. #define cn cout << "NO"
  10. #define nl "\n"
  11. #define fi first
  12. #define se second
  13. #define cin(v) for (int i = 0; i < n, cin >> v[i]; i++)
  14. #define cout(v) for (int i = 0; i < v.size(), cout << v[i] << " "; i++)
  15. #define all(v) v.begin(), v.end()
  16. #define sz(s) s.size()
  17.  
  18. void sherry()
  19. {
  20.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  21. #ifndef ONLINE_JUDGE
  22.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  23. #endif
  24. }
  25. ll n;
  26. vector<ll> a;
  27. vector<vector<int>> dp;
  28. int rec(int idx, int prev)
  29. {
  30.     if (idx == n)
  31.         return 0;
  32.     int &ret = dp[idx][prev];
  33.     if (~ret)
  34.         return ret;
  35.     ret = 1e9;
  36.     if (a[idx] == 0)
  37.         return ret = 1 + rec(idx + 1, a[idx]);
  38.     if (a[idx] == 1 || a[idx] == 2)
  39.         return ret = (a[idx] == prev) + rec(idx + 1, (a[idx] == prev ? 0 : a[idx]));
  40.     if (a[idx] == 3)
  41.     {
  42.         if (prev == 1)
  43.             ret = min(ret, rec(idx + 1, 2));
  44.         else if (prev == 2)
  45.             ret = min(ret, rec(idx + 1, 1));
  46.         else
  47.             ret = min({ret, rec(idx + 1, 1), rec(idx + 1, 2)});
  48.     }
  49.     return ret;
  50. }
  51. void solve()
  52. {
  53.     cin >> n;
  54.     a.resize(n);
  55.     cin(a);
  56.     dp.assign(n, vector<int>(4, -1));
  57.     cout << rec(0, 0);
  58. }
  59. int main()
  60. {
  61.     sherry();
  62.     int t = 1;
  63.     // cin >> t;
  64.     while (t--)
  65.         solve();
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement