蓝桥杯每日一题2023.9.10

桃扇骨 2024-03-04 08:03 31阅读 0赞

[蓝桥杯2023年第十四届省赛真题-接龙数列 - C语言网 (dotcpp.com)][2023_-_ - C_ _dotcpp.com]

### 题目描述 ###

对于一个长度为 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，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

### 分析 ###

类似于最长上升子序列问题

可以将倒数第二个数（以a\[j\]结尾)选哪个数将集合分成若干类（不选直到选a\[i - 1\]那个数）

f\[i\]表示所有以a\[i\]结尾的接龙子序列的集合

第j个数的最后一位等于当前这个数的第一位

超时代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    char s[N], l[N], r[N];
    long long n, res, f[N];
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> s;
    		l[i] = s[0], r[i] = s[strlen(s) - 1];
    	}
    	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[j] + 1, f[i]);
    			res = max(res, f[i]);
    		}
    	}
    	cout << n - res;
    	return 0;
    }

定义dp\[i\]为以dp\[i\]结尾的最长接龙数， 用总长度减去最长的接龙数为需要删去的个数

以l\[i\]结尾表示下一个数的开头是l\[i\]故下一个数结尾是r\[i\]，故可以l\[i\] + 1

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    char s[N];
    long long n, res, dp[N];
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> s;
    		int l = s[0] - '0', r = s[strlen(s) - 1] - '0';
    		dp[r] = max(dp[r], dp[l] + 1);
    		res = max(res, dp[r]);
    	}
    	cout << n - res;
    	return 0;
    }

[2023_-_ - C_ _dotcpp.com]: https://www.dotcpp.com/oj/problem3152.html