fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define vi vector<int>
  4. #define vl vector<long long>
  5. #define pll pair<ll,ll>
  6. #define pii pair<int,int>
  7.  
  8. #define all(v) (v).begin(),(v).end()
  9. #define allr(v) (v).rbegin(),(v).rend()
  10.  
  11. #define ll long long
  12. #define int long long
  13. #define el "\n"
  14.  
  15. const int N = 3e5+5, mod = 1e9+7;
  16.  
  17. #define Hossiny ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  18.  
  19. using namespace std;
  20.  
  21. /*
  22. <<< مَنْ عَمِلَ صَالِحًا مِّن ذَكَرٍ أَوْ أُنثَىٰ وَهُوَ مُؤْمِنٌ فَلَنُحْيِيَنَّهُ حَيَاةً طَيِّبَةً ۖ وَلَنَجْزِيَنَّهُمْ أَجْرَهُم بِأَحْسَنِ مَا كَانُوا يَعْمَلُونَ >>>
  23. */
  24.  
  25. int n;
  26. vector<int> v;
  27. int dp[N][7];
  28. vector<int> adj[7];
  29.  
  30.  
  31. int solve(int idx,int prev){
  32.     if(idx==n) return 0;
  33.     int &ans = dp[idx][prev];
  34.     if(ans!=-1) return ans;
  35.  
  36.     ans = 1e18;
  37.         if(prev==0){
  38.             for(int i=1;i<=6;i++){
  39.                 if(v[idx]==i) ans = min(ans,solve(idx+1,i));
  40.                 else ans = min(ans,solve(idx+1,i)+1);
  41.             }
  42.         }
  43.         else{
  44.             for(auto i:adj[prev]){
  45.                 if(v[idx]==i) ans = min(ans,solve(idx+1,i));
  46.                 else ans = min(ans,solve(idx+1,i)+1);
  47.             }
  48.         }
  49.     return ans;
  50.  
  51. }
  52.  
  53. void testCase() {
  54.     cin >> n;
  55.     v.resize(n);
  56.     for(int i=0;i<n;i++) cin >> v[i];
  57.     memset(dp,-1,sizeof(dp));
  58.     cout << solve(0,0) << el;
  59. }
  60.  
  61. int32_t main() {
  62.     Hossiny
  63.     for(int i=1;i<=6;i++){
  64.         for(int j=1;j<=6;j++){
  65.             if(j!=i && j!=7-i)
  66.                 adj[i].push_back(j);
  67.         }
  68.     }
  69.     int t=1;
  70.     cin>>t;
  71.     while(t--) testCase();
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 20092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gmZoka
language:
C++ (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!