目录
E: 接龙数列
原题
时间限制: 1s 内存限制: 256MB
题目描述
对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。
输出格式
一个整数代表答案。
样例输入
5
11 121 22 12 2023
样例输出
1
提示
删除 22，剩余 11, 121, 12, 2023 是接龙数列。
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
错误版
思路: 求最长不连续的接龙数列的长度L, 输出 n - L
- 求当前数的前导数字上次出现的地方, 并更新f[]
- 更新当前数字的后导数字x对应的 pre[x]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int f[N];
int pre[10]; // 数字上一次出现的位置
string v[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i];
f[i] = 1;
}
int res = 0;
pre[v[1][v[1].size()-1] - '0'] = 1;
for(int i = 2; i <= n; ++i){
int h = v[i][0] - '0', t = v[i][v[i].size()-1] - '0';
f[i] = max(f[i], f[pre[h]]+1);
res = max(res, f[i]);
pre[t] = i;
}
cout << n-res;
return 0;
}
改正版
经朋友指正, 我意识到这不是最优解
那上面哪里有问题呢? 可以举个例子
5
12 21 71 123 345按上面的写法,输出2,
因为当71出现后, pre[1]更新为3 (即上一次以1结尾的数的位置更新为71的下标)
按此思路最终最长的接龙数列是"71 123 345", 并不是全局最优解, 71的出现让后面的数忘记了在71之前以1结尾的其他数, 因此陷入了局部最优解
改进后新增了一个preLen[], preLen[i]表示当前以数字i结尾的接龙数组的最大长度
这样在上面的71出现时, 因为"12 21"的接龙长度大于"71"的接龙长度, 所以不更新pre[], 仿佛71从未来过一般; 否则就更新.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int f[N]; //f[i]: 以第i个字符串结尾的接龙数列的长度
int pre[10]; //数字上一次出现的位置
int preLen[10]; //preLen[i]:当前以数字i结尾的接龙最大长度
string v[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> v[i];
f[i] = 1;
}
int res = 0;
int t = v[1][v[1].size()-1] - '0';
pre[t] = 1, preLen[t] = 1;
for(int i = 2; i <= n; ++i){
int h = v[i][0] - '0', t = v[i][v[i].size()-1] - '0';
f[i] = f[pre[h]]+1;
res = max(res, f[i]);
if(preLen[t] < f[i]) pre[t] = i, preLen[t] = f[i];
}
cout << n-res;
return 0;
}
DP写法
也可以用DP改进
f[i][j]: 前i个字符串中, 以数字j结尾的接龙数列最大长度
最后只需要取max{f[n][0~9]}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
string v[N];
int f[N][10]; //f[i][j]: 前i个字符串中, 以数字j结尾的接龙数列最大长度
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> v[i];
for(int i = 1; i <= n; ++i){
for(int j = 0; j <= 9; ++j) f[i][j] = f[i-1][j];
int h = v[i][0] - '0', t = v[i][v[i].size()-1] - '0';
f[i][t] = max(f[i][t], f[i-1][h]+1);
}
int res = 0;
for(int i = 0; i <= 9; ++i) res = max(res, f[n][i]);
cout << n-res;
return 0;
}