D - Swap and Erase
Source: atcoder
Difficulty: 700

Problem Statement
There is a sequence
A = (A_1,\ldots,A_N)
. You can perform the following two types of operations any number of times in any order:
Let
K
be the length of
A
just before the operation. Choose an integer
i
such that
1 \leq i \leq K-1
, and swap the
i
-th and
(i+1)
-th elements of
A
.
Let
K
be the length of
A
just before the operation. Choose an integer
i
such that
1 \leq i \leq K
and all the values from the
1
-st through the
i
-th elements of
A
are equal, and delete all the elements from the
1
-st through the
i
-th of
A
.
Find the minimum total number of operations required to make
A
an empty sequence.
You are given
T
test cases; solve each of them.
Constraints
1\leq T\leq 10^5
2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
The sum of
N
over all test cases is at most
2\times 10^5
.
All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each case is given in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print the answer for each test case in order, separated by newlines.
Sample Input 1
3
5
1 1 2 1 2
4
4 2 1 3
11
1 2 1 2 1 2 1 2 1 2 1
Sample Output 1
3
4
8
For the 1st test case,
A
can be made empty by the following three operations:
Swap the 3rd and 4th elements of
A
. Now,
A
is
(1,1,1,2,2)
.
Delete the 1st through 3rd elements of
A
. Now,
A
is
(2,2)
.
Delete the 1st through 2nd elements of
A
. Now,
A
is an empty sequence.
For the 2nd test case,
A
can be made empty by deleting the 1st element four times. Also, it is impossible to make
A
empty in three or fewer operations.

C++ solution:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=1e9;
int a[N],f[N][2];
int n,m,ans;
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[1][0]=1,f[1][1]=inf;
	for(int i=2;i<=n;i++){
		f[i][0]=min(f[i-1][0]+(a[i]!=a[i-1]),f[i-1][1]+(a[i]!=a[i-2]));
		f[i][1]=1+(a[i]!=a[i-1])+f[i-2][0]+(a[i]!=a[i-2]);
		if(i>2) f[i][1]=min(f[i][1],1+(a[i]!=a[i-1])+f[i-2][1]+(a[i]!=a[i-3]));
	}
	cout<<min(f[n][0],f[n][1])<<"\n";
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const inf = 1 << 60

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	T := readInt(scanner)

	for t := 0; t < T; t++ {
		N := readInt(scanner)
		A := make([]int, N)
		for i := 0; i < N; i++ {
			A[i] = readInt(scanner)
		}

		dp := make([]int, N)
		dp0 := make([]int, N)
		for i := 0; i < N; i++ {
			dp[i] = inf
			dp0[i] = inf
		}

		dp[0] = 1
		if N > 1 {
			dp0[1] = 3
		}

		for i := 0; i < N-1; i++ {
			if i+1 < N {
				if A[i] == A[i+1] {
					if dp[i] < dp[i+1] {
						dp[i+1] = dp[i]
					}
				} else {
					if dp[i]+1 < dp[i+1] {
						dp[i+1] = dp[i] + 1
					}
				}
			}
			if i > 0 && i+1 < N {
				if A[i-1] == A[i+1] {
					if dp0[i] < dp[i+1] {
						dp[i+1] = dp0[i]
					}
				} else {
					if dp0[i]+1 < dp[i+1] {
						dp[i+1] = dp0[i] + 1
					}
				}
			}
			if i < N-2 {
				if A[i] == A[i+2] {
					if dp[i]+2 < dp0[i+2] {
						dp0[i+2] = dp[i] + 2
					}
				} else {
					if dp[i]+3 < dp0[i+2] {
						dp0[i+2] = dp[i] + 3
					}
				}
				if i > 0 {
					if A[i-1] == A[i+2] {
						if dp0[i]+2 < dp0[i+2] {
							dp0[i+2] = dp0[i] + 2
						}
					} else {
						if dp0[i]+3 < dp0[i+2] {
							dp0[i+2] = dp0[i] + 3
						}
					}
				}
			}
		}

		ans := dp[N-1]
		if dp0[N-1] < ans {
			ans = dp0[N-1]
		}
		fmt.Println(ans)
	}
}

func readInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.NoSuchElementException;

public class Main implements Runnable { // Runnableを実装する
	public static void main(String[] args) {
		new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); // 16MBスタックを確保して実行
	}
	
	final static long mod=998244353;
	int MAX=10000;
	long[] fac=new long[MAX];
	long[] ifac=new long[MAX];
	long[] inv=new long[MAX];
	{
		Arrays.fill(fac, 1);
		Arrays.fill(ifac, 1);
		Arrays.fill(inv, 1);
		for (int i=2;i<MAX;++i) {
			fac[i]=i*fac[i-1]%mod;
			inv[i]=mod-(mod/i)*inv[(int)(mod%i)]%mod;
			ifac[i]=inv[i]*ifac[i-1]%mod;
		}
	}
	
	static long pow(long a, long n) {
		if (n==0) return 1;
		return pow(a*a%mod,n/2)*(n%2==1?a:1)%mod;
	}
	
	static long inv(long a) {
		return pow(a,mod-2);
	}
	
	long comb(int n, int k) {
		if (k<0||n-k<0)return 0;
		return fac[n]*ifac[n-k]%mod*ifac[k]%mod;
	}
	
	
	public void run() {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int T=sc.nextInt();
		for (int testcase=0;testcase<T;testcase++) {
			int N=sc.nextInt();
			int[]A=new int[N];
			for(int i=0;i<N;++i) {
				A[i]=sc.nextInt();
			}
			long INF=Long.MAX_VALUE/3;
			long[][]dp=new long[N+1][2];
			//dp[i][flag]=flagは(i-2,i-1)をswapしたかどうか, いくつ得したか
			for(int i=0;i<dp.length;++i) {
				for(int j=0;j<dp[i].length;++j) {
					dp[i][j]=-INF;
				}
			}
			dp[0][0]=0;
			for(int i=0;i<N;++i) {
				for(int swapped=0;swapped<=1;++swapped) {
					if (dp[i][swapped]==-INF)continue;
					int last=i>0?A[i-1]:-1;
					if (swapped==1&&i>=0) {
						last=A[i-2];
					}
					{//何もしない
						dp[i+1][0]=Math.max(dp[i+1][0], dp[i][swapped]+(last==A[i]?1:0));
					}
					if(i+2<N&&A[i]!=A[i+1]){//swap(A[i],A[i+1])
						dp[i+2][1]=Math.max(dp[i+2][1], dp[i][swapped]+((last==A[i+1])?1:0)-1);
					}
				}
			}
			
			long max=0;
			max=Math.max(dp[N][0], max);
			max=Math.max(dp[N][1], max);
			long ans=N-max;
			pw.println(ans);
		}
		
		pw.close();
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		return (int) nextLong();
	}
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
let currentLine = 0;

rl.on('line', (line) => {
    input.push(line);
});

rl.on('close', () => {
    solve();
});

function solve() {
    currentLine = 0;
    const T = parseInt(input[currentLine++]);
    for (let _ = 0; _ < T; _++) {
        const N = parseInt(input[currentLine++]);
        const A = input[currentLine++].split(' ').map(Number);
        
        const dp = new Array(N).fill(Infinity);
        const dp0 = new Array(N).fill(Infinity);
        
        dp[0] = 1;
        if (N >= 2) {
            dp0[1] = 3;
        }
        
        for (let i = 0; i < N - 1; i++) {
            if (A[i] === A[i + 1]) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i]);
            } else {
                dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
            }
            if (i !== 0) {
                if (A[i - 1] === A[i + 1]) {
                    dp[i + 1] = Math.min(dp[i + 1], dp0[i]);
                } else {
                    dp[i + 1] = Math.min(dp[i + 1], dp0[i] + 1);
                }
            }
            if (i < N - 2) {
                if (A[i] === A[i + 2]) {
                    dp0[i + 2] = Math.min(dp0[i + 2], dp[i] + 2);
                } else {
                    dp0[i + 2] = Math.min(dp0[i + 2], dp[i] + 3);
                }
                if (i !== 0) {
                    if (A[i - 1] === A[i + 2]) {
                        dp0[i + 2] = Math.min(dp0[i + 2], dp0[i] + 2);
                    } else {
                        dp0[i + 2] = Math.min(dp0[i + 2], dp0[i] + 3);
                    }
                }
            }
        }
        
        const ans = Math.min(dp[N - 1], dp0[N - 1] || Infinity);
        console.log(ans);
    }
}

Python solution:
import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    N=int(input())
    A=list(map(int,input().split()))

    A=[1<<60]+[1<<59]+A

    DP0=[1<<60]*(N+2)
    DP1=[1<<60]*(N+2)
    DP2=[1<<60]*(N+2)

    DP0[1]=0

    for i in range(2,N+2):
        if A[i]==A[i-1]:
            DP0[i]=min(DP0[i],DP0[i-1])
        else:
            DP0[i]=min(DP0[i],DP0[i-1]+1)

        if i+1<len(A) and A[i-1]==A[i+1]:
            DP1[i]=min(DP1[i],DP0[i-1]+1)
        else:
            DP1[i]=min(DP1[i],DP0[i-1]+2)

        DP2[i]=min(DP2[i],DP1[i-1]+1)

        if A[i-2]==A[i]:
            DP0[i]=min(DP0[i],DP2[i-1])
        else:
            DP0[i]=min(DP0[i],DP2[i-1]+1)

        if i+1<len(A) and A[i-2]==A[i+1]:
            DP1[i]=min(DP1[i],DP2[i-1]+1)
        else:
            DP1[i]=min(DP1[i],DP2[i-1]+2)

    print(min(DP0[-1],DP1[-1],DP2[-1]))

Ruby solution:
def solve_case(n, a)
  return 1 if n == 1  # Base case: single element

  dp = Array.new(n, Float::INFINITY)
  dp0 = Array.new(n, Float::INFINITY)

  # Initialize base cases
  dp[0] = 1
  dp0[1] = 3 if n >= 2

  (0...n-1).each do |i|
    # Update dp[i+1] from dp[i]
    if a[i] == a[i+1]
      dp[i+1] = [dp[i+1], dp[i]].min
    else
      dp[i+1] = [dp[i+1], dp[i] + 1].min
    end

    # Consider swap from dp0[i] if possible
    if i > 0 && i+1 < n
      if a[i-1] == a[i+1]
        dp[i+1] = [dp[i+1], dp0[i]].min
      else
        dp[i+1] = [dp[i+1], dp0[i] + 1].min
      end
    end

    # Update dp0[i+2] if within bounds
    if i+2 < n
      if a[i] == a[i+2]
        dp0[i+2] = [dp0[i+2], dp[i] + 2].min
      else
        dp0[i+2] = [dp0[i+2], dp[i] + 3].min
      end

      # Consider swap from dp0[i] if possible
      if i > 0 && i+2 < n
        if a[i-1] == a[i+2]
          dp0[i+2] = [dp0[i+2], dp0[i] + 2].min
        else
          dp0[i+2] = [dp0[i+2], dp0[i] + 3].min
        end
      end
    end
  end

  [dp[n-1], dp0[n-1]].min
end

def main
  input = $stdin.each_line.to_a
  t = input[0].to_i
  ptr = 1

  t.times do
    n = input[ptr].to_i
    ptr += 1
    a = input[ptr].split.map(&:to_i)
    ptr += 1
    puts solve_case(n, a)
  rescue => e
    puts "Error processing test case: #{e}"
  end
end

main