題目描述

對(duì)于一個(gè)長(zhǎng)度為 K 的整數(shù)數(shù)列：A1, A2, . . . , AK，我們稱之為接龍數(shù)列當(dāng)且僅當(dāng) Ai?的首位數(shù)字恰好等于 Ai?1?的末位數(shù)字 (2 ≤ i ≤ K)。

例如 12, 23, 35, 56, 61, 11 是接龍數(shù)列；12, 23, 34, 56 不是接龍數(shù)列，因?yàn)?56的首位數(shù)字不等于 34 的末位數(shù)字。所有長(zhǎng)度為 1 的整數(shù)數(shù)列都是接龍數(shù)列。

現(xiàn)在給定一個(gè)長(zhǎng)度為 N 的數(shù)列 A1, A2, . . . , AN，請(qǐng)你計(jì)算最少?gòu)闹袆h除多少個(gè)數(shù)，可以使剩下的序列是接龍序列？

輸入格式

第一行包含一個(gè)整數(shù) N。

第二行包含 N 個(gè)整數(shù) A1, A2, . . . , AN。

輸出格式

一個(gè)整數(shù)代表答案。

樣例輸入

5 11 121 22 12 2023

樣例輸出

1

思路:

找到最長(zhǎng)的接龍數(shù)列的長(zhǎng)度 len, 那么 n - len 就是最小操作數(shù)。

可以使用 dp 找到最長(zhǎng)的接龍數(shù)列

首先定義狀態(tài)所代表的子集:

f[i][j]: 在前 i 個(gè)數(shù)中結(jié)尾數(shù)字為 j 的所有數(shù)列

定義子集的屬性為最大長(zhǎng)度。

接下來(lái)我們推導(dǎo)狀態(tài)轉(zhuǎn)移:

對(duì)于數(shù)字 a, 我們用 a.first 表示其首位數(shù)字, b.first 表示其末尾數(shù)字, 假設(shè)我們當(dāng)前集合準(zhǔn)備選取數(shù)字 k:

那么對(duì)于數(shù)字 k 這個(gè)對(duì)象, 有選和不選兩種情況

如果不選的話: f[i][k.second] = f[i - 1][k.second]

如果選的話: f[i][k.second] = f[i - 1][k.first]

于是有 f[i][k.second] = max(f[i - 1][k.second], f[i - 1][k.first])

由于我們要取 f[n][0] ~ f[n][9] 的最大值, 那么需要在每次循環(huán)前可以先計(jì)算出不選時(shí)的答案 f[i][j]=f[i- 1][j] (否則會(huì)全部 WA 暴零):