网站开发工资淄博,网站备案主体授权书,辽宁建设工程造价信息网,受欢迎的永州网站建设接龙数列
题目描述 对于一个长度为 K 的整数数列#xff1a;A1, A2, . . . , AK#xff0c;我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列#xff1b;12, 23, 34, 56 不是接龙数列#xf…接龙数列
题目描述 对于一个长度为 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 ≤ 1051 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
动态规划
dp[i]表示以i为数字最后一位的最长接龙数列长度 x是该数最高位y表示最低位 转移方程dp[y]max(dp[x]1,dp[y]);dp[x]1表示选择当前数dp[y]表示不选择当前数
#includeiostream
#includecstring
using namespace std;
int main()
{int dp[15]{0};int n,m1;cinn;for(int i0;in;i){string s;cins;int xs[0]-0,ys[s.size()-1]-0;dp[y]max(dp[x]1,dp[y]);mmax(m,dp[y]);}coutn-mendl;return 0;
}
