两维
第一维,存访问到第几个数,这一维度可以优化
第二维,存当前的接龙尾部是哪个数(tail)
当前i的头部数(top)求出来后,可以对上一个tail等于当前top的状态数(这里表示为最少减去数,表示为长度也可以,这时候就求max)f[i-1][top]以及f[i-1][tail]+1取min(因为从上次tail出现更新到tail未必比从top更新到tial要大)
而对于当前的不等于tail的j,直接按上一次出现+1就行
最后取一个最小值
import java.io.*;
public class Main{
static int n;
static final int N=100010;
static int[] a=new int[N];
static int[][] f=new int[N][10];
static int get_top(int x) {
while(x>=10)x/=10;
return x;
}
static int get_tail(int x) {
return x%10;
}
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
String[] s1=br.readLine().split(" ");
for(int i=1;i<=n;i++)a[i]=Integer.parseInt(s1[i-1]);
for(int i=1;i<=n;i++) {
int top=get_top(a[i]);
int tail=get_tail(a[i]);
f[i][tail]=Math.min(f[i-1][tail]+1,f[i-1][top]);
for(int j=0;j<=9;j++) {
if(j!=tail)f[i][j]=f[i-1][j]+1;
}
}
int res=Integer.MAX_VALUE;
for(int i=0;i<=9;i++)res=Math.min(res,f[n][i]);
System.out.println(res);
}
}