算法1
(暴力枚举) $O(n^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N], g[N];
int n;
int l[N], r[N];
int main()
{
cin >> n;
char str[20];
for(int i = 1; i <= n; i ++ )
{
cin >> str;
l[i] = str[0] - '0';
r[i] = str[strlen(str) - 1] - '0';
}
int res = 0;
for(int i = 1; i <= n; i ++ )
{
f[i] = 1;
for(int j = 1; j < i; j ++ )
{
if(l[i] == r[j])
{
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << n - res << endl;
return 0;
}
算法2
(开辅助空间) $O(n)$
利用g数组存放数字k结尾的接龙序列的最大长度。无需对前i-1个数字进行遍历
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int l[N], r[N];
int g[N];//用于存放以k数字结尾的接龙序列的最大长度
int f[N];
int main()
{
int n;
cin >> n;
char str[20];
for(int i = 1; i <= n; i ++ )
{
cin >> str;
l[i] = str[0] - '0';
r[i] = str[strlen(str) - 1] - '0';
}
int res = 0;
for(int i = 1; i <= n; i ++ )
{
f[i] = g[l[i]] + 1;
g[r[i]] = max(g[r[i]], f[i]);
res = max(res, f[i]);
}
cout << n - res << endl;
return 0;
}