tr

[L, R] aralığındaki karelerin aynı renkte olduğunu varsayalım, o zaman renkleri \(\mathbf{c_L}\) ve \(\mathbf{c_R}\) ikilisinden biri olmalıdır. \(\mathbf{f}\)'i [L, R] aralığını tek renk yapmak için gereken minimum hamle sayısı olarak tanımlayabiliriz.

\(\mathbf{f}\)(L,R,0) aralığı \(\mathbf{c_L}\) rengi yapmak için gereken minimum hamle sayısını veren fonksiyon.

\(\mathbf{f}\)(L,R,0) aralığı \(\mathbf{c_R}\) rengi yapmak için gereken minimum hamle sayısını veren fonksiyon.

\(\mathbf{f}\) fonksiyonu recursive çalışıyor ve çözümü daha verimli hale getirmek için dynamic programming kullanıyor.

Sopanın uzunluğu 1 ise, sopa tek renklidir diyebiliriz ve sopanın rengini değiştirmek gerekmez. \(\mathbf{n}\) uzunluğundaki bir sopanın rengini değiştirmek için gereken minimum hamle sayısını biliyor olduğumuzu varsayalım, bu durumda \(\mathbf{n+1}\) uzunluğundaki bir sopa için geriye kalan parça sopanın sağ ya da sol ucu olmalı. Öyleyse sopanın uçları aynı renkte değilse, bir kere daha boyama yapmak gerekmektedir.

en

Suppose squares [L, R] are painted with the same color, then they are either of color \(\mathbf{c_L}\) or \(\mathbf{c_R}\). We can define \(\mathbf{f}\) as the minimum number of moves required to make the segment [L, R] monochromic:

\(\mathbf{f}\)(L,R,0) is the function to find the least moves required to make the segment having color \(\mathbf{c_L}\).

\(\mathbf{f}\)(L,R,1) is the function to find the least moves required to make the segment having color \(\mathbf{c_R}\).

The function finds it recursively, dynamic programming is used to make it more efficient.

It's obvious that when the length of the stick is 1, the stick is uniform, hence it's not needed to change the color of the stick. Assume that the it's known how many moves needed to color the stick of length \(\mathbf{n}\). To find how many moves needed to find the stick of length \(\mathbf{n+1}\), the next part is either colored to either the left tip of the stick or the right tip. If tips aren't the same color, it's needed to change the color one more time.

#include <bits/stdc++.h>

using namespace std;

int dp[5000][5000][2];
int arr[5000];

int f(int l, int r, bool isLeft){
    if(l==r) return 0;

    if(isLeft && dp[l][r][1]!=-1) return dp[l][r][1];
    if(!isLeft && dp[l][r][0]!=-1) return dp[l][r][0];

    if(isLeft){
        int ret1 = f(l+1, r, true);
        int ret2 = f(l+1, r, false);
        if(arr[l]!=arr[l+1]) ret1++;
        if(arr[l]!=arr[r]) ret2++;
        dp[l][r][1] = min(ret1, ret2);
        return dp[l][r][1];
    } 
    else {
        int ret1 = f(l, r-1, true);
        int ret2 = f(l, r-1, false);
        if(arr[l]!=arr[r]) ret1++;
        if(arr[r-1]!=arr[r]) ret2++;
        dp[l][r][0] = min(ret1, ret2);
        return dp[l][r][0];
    } 

}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    for(int i=0;i<5000;i++){
        for(int j=0;j<5000;j++){
            dp[i][j][1] = -1;
            dp[i][j][0] = -1;
        }
    }

    cout<<min(f(0, n-1, false), f(0, n-1, true));

}