P9242 接龙数列

一、题目描述

P9242 [蓝桥杯 2023 省 B] 接龙数列

二、算法简析

核心思想：动态规划

题目要我们求删除数的最小个数。可以转变问题，求能形成的接龙数列的最大长度 $MaxLength$，$n-MaxLength$ 即为所求。
由题意可知，我们只需要关注每个数的首、末位数字。规定，$A[i]$ 表示下标为 $i$ 的数，$A[i].l$ 和 $A[i].r$ 分别表示 $A[i]$ 的首、末位数字。
令 $dp[i+1][j]=$ 前 $i+1$ 个数以 $j$ 结尾的接龙数列的最大长度。有两种情况：

• 1、若 $A[i].r\ne j$，则 $A[i]$ 不能加入数列，即 $dp[i+1][j]=dp[i][j]$。
• 2、若$A[i].r==j$，则 $A[i]$ 可以加入或不加入数列，即 $dp[i+1][j]=max(dp[i][j],dp[i][A[i].l])$。

我们可以压缩至一维数组：
$$dp[A[i].l]=max(dp[A[i].l],dp[A[i].r]+1)$$

---

三、本题代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

int n, dp[10];
vector<P> A;

P quickin(void)
{
P ret;
bool flag = true;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while ('0' <= ch && ch <= '9')
{
if (flag)
{
ret.first = ret.second = ch - '0';
flag = false;
}
else
ret.second = ch - '0';
ch = getchar();
}
return ret;
}

int solve(void)
{
for (int i = 0; i < n; i++)
{
dp[A[i].second] = max(dp[A[i].second], dp[A[i].first] + 1);
}
int ans = 0;
for (int i = 0; i < 10; i++)
ans = max(ans, dp[i]);
return ans;
} 

int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif

cin >> n;
for (int i = 0; i < n; i++)
A.push_back(quickin());

cout << n - solve() << endl;

return 0;
} 

---

完

原文地址：https://blog.csdn.net/hydrogend/article/details/136150129

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！