34 lines
850 B
C++
34 lines
850 B
C++
// lanqiao3712 接龙数列
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 1e5 + 10;
|
||
int ft[N], bk[N], dp[N];
|
||
/*
|
||
ft[i]第i个元素的首数字、bk［i］第i个元素尾数字
|
||
类LIS问题的DP解法-时间复杂度0(n^2)
|
||
状态 dp[i] 以第主个元素作为结尾的最长接龙数列的长度
|
||
状态转移方程 dp[i] = max(dp[i], dp[j]+1);
|
||
*/
|
||
int main(){
|
||
int n; cin >> n;
|
||
string s;
|
||
for(int i = 1; i<=n; i++){
|
||
cin >> s;
|
||
ft[i] = s.front() - '0', bk[i] = s.back() - '0', dp[i] = 1;
|
||
}
|
||
int mx = 1;
|
||
for(int i = 2; i <= n; i++){
|
||
for(int j = 1; j < i; j++){
|
||
if(bk[j] == ft[i]){
|
||
dp[i] = max(dp[i], dp[j] + 1);
|
||
}
|
||
mx = max(mx, dp[i]);
|
||
}
|
||
}
|
||
cout << n - mx << endl;
|
||
return 0;
|
||
}
|
||
/* test samples 易超时
|
||
5
|
||
11 121 22 12 2023
|
||
*/ |