问题描述

对于一个长度为 K的整数数列：A1,A2,...,AK我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1的末位数字 (2≤i≤K)。

例如 12,23,35,56,61,1112,23,35,56,61,11 是接龙数列；12,23,34,5612,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。

所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A1,A2,...,AN请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 1,2,…,A1​,A2​,…,AN​。

输出格式

一个整数代表答案。

样例输入

5

11 121 22 12 2023

样例输出

1

样例说明

删除 22，剩余 11,121,12,2023是接龙数列。

评测用例规模与约定

对于 2020% 的数据，1≤N≤20。

对于 5050% 的数据，1≤N≤10000。

对于 100100% 的数据，1≤N≤1000000，1≤Ai​≤10^9。所有 Ai​ 保证不包含前导 0

运行限制

语言最大运行时间最大运行内存C++1s256MC1s256MJava2s256MPython33s256MPyPy33s256MGo3s256MJavaScript3s256M

#include // 包含输入输出流库

#include // 包含处理字符串的库

#include // 包含一些算法库函数

using namespace std;

const int N=1e5+10; // 定义常量 N = 100010

int a[N],b[N],f[N],g[N]; // 声明四个数组a、b、f、g，每个数组大小为 N

int main()

{

int n; // 声明变量 n

cin>>n; // 输入变量 n，表示接下来会有 n 个数字串

char s[100]; // 声明字符数组 s，用于存储输入的数字串

for(int i=0;i

{

cin>>s; // 输入数字串，将其存储在字符数组 s 中

a[i]=s[0]-'0'; // 将数字串的首字符转换为整数，存储在数组 a 中

b[i]=s[strlen(s)-1]-'0'; // 将数字串的末字符转换为整数，存储在数组 b 中

}

int mx=0; // 声明变量 mx，用于记录最大的循环长度，初始化为 0

for(int i=0;i

{

f[i]=1; // 将 f 数组的当前元素初始化为 1

f[i]=max(f[i],g[a[i]]+1); // 更新 f 数组的当前元素，取 f[i] 和 g[a[i]]+1 中的较大值

g[b[i]]=max(f[i],g[b[i]]); // 更新 g 数组的当前元素，取 f[i] 和 g[b[i]] 中的较大值

}

for(int i=0;i

{

mx=max(mx,f[i]); // 更新最大循环长度 mx，取 mx 和 f[i] 中的较大值

}

cout<

return 0; // 返回 0，表示程序运行成功

}

 

根据输入数据分析，输入的第一行是一个数字5，表示接下来要输入的数字个数。接着的一行是以空格分隔的5个数字字符串，分别是11、121、22、12和2023。下面是对这些数据进行处理的解析过程：

首先，我们定义一些变量和数组：

const int N = 100010;

int n;

int f[N], g[N];

int l[N], r[N];

N 是一个常量，表示数组的最大长度。n 是一个整数，用于记录输入数字的个数。f 和 g 是两个整数数组，用于存储计算结果。l 和 r 是两个整数数组，用于存储输入数字的首位和末位。

然后，我们读取输入的数字个数：

cin >> n;

接下来，我们读取并处理每个数字字符串：

for (int i = 0; i < n; i++) {

cin >> num;

l[i] = num[0] - '0';

r[i] = num[strlen(num) - 1] - '0';

}

在每次循环中，我们首先读取一个数字字符串 num，然后将其首位和末位转换为数字，并分别存储到数组 l 和 r 中。

接下来，我们进行动态规划计算和更新：

int res = 0;

for (int i = 0; i < n; i++) {

f[i] = 1;

f[i] = max(f[i], g[l[i]] + 1);

g[r[i]] = max(f[i], g[r[i]]);

res = max(res, f[i]);

}

在每次循环中，我们首先将 f[i] 初始化为1，表示以当前数字结尾的最长序列长度至少为1。

然后，我们使用状态转移方程 f[i] = max(f[i], g[l[i]] + 1) 来更新 f[i] 的值。该方程的意思是，如果存在以数字 l[i] 结尾的序列，那么可以将当前数字接在其后形成一个更长的序列。因此，我们将当前 f[i] 和 g[l[i]] + 1 的较大值赋给 f[i]，以记录以当前数字结尾的最长序列长度。

接着，我们使用状态转移方程 g[r[i]] = max(f[i], g[r[i]]) 来更新 g[r[i]] 的值。该方程的意思是，如果存在以数字 r[i] 结尾的序列，那么需要更新 g[r[i]] 的值为当前的最大值，即 f[i] 和当前 g[r[i]] 的较大值。

最后，我们通过比较 res 和 f[i] 的值来更新最终结果 res，以记录整个序列中的最长不符合条件的数字的个数。

最后，我们输出结果 n - res，即不符合条件的数字的个数：

cout << n - res << endl;

以上就是根据输入数据进行解析和处理的过程分析，展示了代码的功能和执行流程。

以下是正确的执行过程：

首先，输入数字序列的长度为 5。接着，逐个输入每个数字并提取首位数字和末位数字。

对于数字 11，其首位数字和末位数字均为 1，存储在 l[0] 和 r[0] 中。对于数字 121，其首位数字为 1，末位数字为 1，存储在 l[1] 和 r[1] 中。对于数字 22，其首位数字和末位数字均为 2，存储在 l[2] 和 r[2] 中。对于数字 12，其首位数字为 1，末位数字为 2，存储在 l[3] 和 r[3] 中。最后一个数字是 2023，其首位数字为 2，末位数字为 3，存储在 l[4] 和 r[4] 中。接着进行动态规划计算，逐个数字计算最长接龙序列长度。

对于数字 11，最长接龙序列长度为 1。对于数字 121，最长接龙序列长度为 2。对于数字 22，最长接龙序列长度为 1。对于数字 12，最长接龙序列长度为 2。对于数字 2023，最长接龙序列长度为 4。 (1 -> 12 -> 22 -> 2023)最终，通过计算最少需要删除的数的个数，得到结果为 5 - 4 = 1。

 

好文阅读

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：