526互联

(已改正)第十四届蓝桥B组省赛回忆版 E: 接龙数列

发布时间 2023-04-09 18:29:28作者: 泥烟

目录

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

  1. 求当前数的前导数字上次出现的地方, 并更新f[]
  2. 更新当前数字的后导数字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;
}

image

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;
}