fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.  dp0[i]: max matches we can get on prefix [1..i] if we have NOT used the removal,
  6.           and we *do* end with a match at i (i.e. after operations, a[i]==b[i]).
  7.  dp1[i]: max matches we can get on prefix [1..i] if we HAVE used the removal,
  8.           and we *do* end with a match at i.
  9.  
  10.  We only need to look at whether the two pairs (a[i-1],b[i-1]) and (a[i],b[i])
  11.  share any value to decide if we can extend a matching "chain" from i-1 to i
  12.  without doing a removal right there.  If they intersect, both dp0 and dp1
  13.  transition by +1.  Otherwise, we can only get a new match at i by "resetting"—
  14.  either by using our one removal at i-1 (transition from dp0 to dp1), or by
  15.  starting fresh after we've already removed (staying in dp1).
  16. */
  17.  
  18. int main(){
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.  
  22.     int T; 
  23.     cin >> T;
  24.     while (T--){
  25.         int n;
  26.         cin >> n;
  27.         vector<int> a(n+1), b(n+1);
  28.         for (int i = 1; i <= n; i++) cin >> a[i];
  29.         for (int i = 1; i <= n; i++) cin >> b[i];
  30.  
  31.         // Base case: at i=1, you cannot match without a neighbor,
  32.         // so dp0=0.  If you choose to remove at i=1 (not really helpful),
  33.         // dp1=0 as well.
  34.         int dp0 = 0, dp1 = 0;
  35.         int answer = 0;
  36.  
  37.         for (int i = 2; i <= n; i++){
  38.             // can we extend a match-chain from (i-1) to i without a removal?
  39.             bool intersect = 
  40.                 a[i] == a[i-1] ||
  41.                 a[i] == b[i-1] ||
  42.                 b[i] == a[i-1] ||
  43.                 b[i] == b[i-1];
  44.  
  45.             int new0, new1;
  46.             if (intersect) {
  47.                 // both states extend
  48.                 new0 = dp0 + 1;
  49.                 new1 = dp1 + 1;
  50.             } else {
  51.                 // can't extend dp0 (no removal used) so we'd have to start fresh:
  52.                 new0 = 1; 
  53.                 // for dp1, either we already removed (dp1) and start fresh, or
  54.                 // we remove right here (dp0 -> dp1) and start fresh: both give dp0+1
  55.                 new1 = max(dp1 + 1, dp0 + 1);
  56.             }
  57.             dp0 = new0;
  58.             dp1 = new1;
  59.             answer = max({answer, dp0, dp1});
  60.         }
  61.  
  62.         // If n==1, you can never match because there is no i+1 to pull from,
  63.         // so answer = 0 in that edge case.
  64.         if (n == 1) answer = 0;
  65.  
  66.         cout << answer << "\n";
  67.     }
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
10
4
1 3 1 4
4 3 2 2
6
2 1 5 3 6 4
3 2 4 5 1 6
2
1 2
2 1
6
2 5 1 3 6 4
3 5 2 3 4 6
4
1 3 2 2
2 1 3 4
8
3 1 4 6 2 2 5 7
4 2 3 7 1 1 6 5
10
5 1 2 7 3 9 4 10 6 8
6 2 3 6 4 10 5 1 7 9
5
3 2 4 1 5
2 4 5 1 3
7
2 2 6 4 1 3 5
3 1 6 5 1 4 2
5
4 1 3 2 5
3 2 1 5 4
stdout
copy 
3
5
1
5
3
7
9
4
6
4
https://ideone.com/X4K8Ea
language:
C++ (gcc 8.3)
created:
3 days 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!