Submission #219295

#TimeUsernameProblemLanguageResultExecution timeMemory
219295rama_pangLamps (JOI19_lamps)C++14
4 / 100
110 ms67020 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;

int N;
string A, B;

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> A >> B;
}

int Solve() {
  vector<array<array<int, 4>, 4>> dp(N + 1); // dp[pos][second_last_operation][last_operation]
  // dp[pos] means A[pos...N] = B[pos...N]
  // operation 0 = skip operation
  // operation 1 = off operation
  // operation 2 = on operation
  // operation 3 = xor operation

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) { 
        dp[i][j][k] = INF;
      }
    }
  }

  dp[0][0][0] = 0;
  for (int pos = 0; pos < N; pos++) {
    // continue extending basic operations

    for (int second_last = 0; second_last < 4; second_last++) {
      for (int last = 0; last < 4; last++) {
        if (A[pos] == B[pos]) { // operation skip (0)
          dp[pos + 1][last][0] = min(dp[pos + 1][last][0], dp[pos][second_last][last]);
        }
        if (B[pos] == '0') { // operation off (1)
          dp[pos + 1][last][1] = min(dp[pos + 1][last][1], (last != 1) + dp[pos][second_last][last]);
        }
        if (B[pos] == '1') { // operation on (2)
          dp[pos + 1][last][2] = min(dp[pos + 1][last][2], (last != 2) + dp[pos][second_last][last]);
        }
        if (A[pos] != B[pos]) { // operation xor (3)
          dp[pos + 1][last][3] = min(dp[pos + 1][last][3], (last != 3) + dp[pos][second_last][last]);
        }
      }
    }

    // mergable operations

    dp[pos + 1][0][1] = min(dp[pos + 1][0][1], dp[pos][1][2]); // off on off (from off off/on off)
    dp[pos + 1][0][2] = min(dp[pos + 1][0][2], dp[pos][2][1]); // on off on (from on on/off on)

    dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][1][2]); // off on xor (from off on/xor xor)
    dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][2][1]); // on off xor (from on off/xor xor)

    dp[pos + 1][0][2] = min(dp[pos + 1][0][2], dp[pos][3][1]); // xor off on (from xor xor/on on)
    dp[pos + 1][0][1] = min(dp[pos + 1][0][1], dp[pos][3][2]); // xor on off (from xor xor/off off)    
  }  

  int res = INF;
  for (int second_last = 0; second_last < 4; second_last++) {
    for (int last = 0; last < 4; last++) {
      res = min(res, dp[N][second_last][last]);
    }
  }

  return res;
}

int main() {
  Read();
  cout << Solve() << "\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...