Quann

用户名：uq_79629066827

访问量：1857

签　名：

2021年老兵

等　　级
排　　名	22721
经　　验	646
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

双指针时间复杂度O(n + m)
浏览：509

你可能喜欢

A+B for Input-Output Practice (IV) （C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

记忆化搜索找最长接龙序列

　　作者: Quann　　　　发表时间：2024-03-23 00:49:59 浏览：1408　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-接龙数列

``` c++
#include <bits/stdc++.h>
#define debug(x) cout << #x << ' ' << x << '\n'
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
const int N = 100010, mod = 1e9 + 7, inf = 0x3f3f3f3f;

int n;

struct info {
	int a, b;
}p[N];

int dp[N][11];

ll dfs(int pos, int sta) {
	if (dp[pos][sta] != -1)	return dp[pos][sta];
	if (pos == n + 1)	return dp[pos][sta] = 0;
	ll res = 0;
	if (sta == 0) {
		res = max(dfs(pos + 1, p[pos].b) + 1, dfs(pos + 1, sta));
	} else {
		if (p[pos].a != sta) {
			res = max(res, dfs(pos + 1, sta));
		} else res = max(dfs(pos + 1, p[pos].b) + 1, dfs(pos + 1, sta));
	}
	return dp[pos][sta] = res;
}

void solve()
{
	memset(dp, -1, sizeof dp);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		int x;	cin >> x;
		p[i].b = x % 10;
		while(x) {
			if (x / 10 == 0)	p[i].a = x;
			x /= 10;
		}
		// 都叠加1是为了空出0状态 来表示是否已经有选择的数
		p[i].a ++;
		p[i].b ++;
	}

cout << n - dfs(1, 0) << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

solve();

return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Quann

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

数列（C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

记忆化搜索找最长接龙序列

评论区

精彩推荐

回文串（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

printf基础练习2 （有点不明白）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

字符逆序（C语言代码）

简单的a+b （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

整除的尾数（C语言代码）

Quann

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

数列 （C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

记忆化搜索 找最长接龙序列

评论区

精彩推荐

回文串 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

printf基础练习2 （有点不明白）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

字符逆序 （C语言代码）

简单的a+b （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

整除的尾数 （C语言代码）

数列（C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

记忆化搜索找最长接龙序列

　　评论区

回文串（C语言代码）

字符逆序（C语言代码）

Tom数（C语言代码）

整除的尾数（C语言代码）