衡阳网站设计ss0734,百度搜索收录,本地wordpress模板编辑器,学科专业建设思路和目标目录
题目链接
题目理解
解题思路
完整代码
重难点解答
*dp数组的具体用法
*对于dp[b]dp[a]1dp[b]?dp[a]1:dp[b]的解释 题目链接 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷
题目理解 这道题让我们求任给的一串数字#xff0c;若想让其变成接龙数列最少需要删除的数字…目录
题目链接
题目理解
解题思路
完整代码
重难点解答
*dp数组的具体用法
*对于dp[b]dp[a]1dp[b]?dp[a]1:dp[b]的解释 题目链接 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷
题目理解 这道题让我们求任给的一串数字若想让其变成接龙数列最少需要删除的数字个数。首先我们要明白什么是接龙数列。接龙数列是前一个数的末位数字与下一个数的第一位相同的数列比如 37、798、888。题目理解起来没什么难度下面我们来讲一下解题思路。
解题思路 这道题目的思路是找出给定数字序列中能够凑成的最长接龙序列然后用总长度减去最长序列的长度即为最少需要删除的数字个数。
定义一个长度为10的数组dp用于记录每个数字作为末位数字时的最长接龙序列长度。遍历输入的数列对于每个数将其首位数字记为a末位数字记为b。使用动态规划的思想更新dp数组中对应的值。dp[b]的值应该是dp[a]1和dp[b]的较大值。同时记录最大的接龙序列长度amount。最后输出n-amount即最少需要删除的数的个数。
完整代码
#includestdio.h
main()
{int a0,b0;//a为数字的首位数b为数字的末数int n0,amount0;//n表示数列中数字个数amount表示最长的接龙数列的数字个数int dp[10]{0},number0;//dp数组用于存储对应位的最长数列长度scanf(%d,n);for(int i0;in;i){scanf(%d,number);bnumber%10;//b为末位数字while(number10)//a为首位数字{anumber/10;number/10;}dp[b]dp[a]1dp[b]?dp[a]1:dp[b];//重点详见文章重难点解答if(dp[b]amount){amountdp[b];}}printf(%d,n-amount);}
重难点解答 *dp数组的具体用法 具体来说我们遍历输入的数字序列。dp[n]就是以数字n在某数字第一次作为末位数出现的接龙数列的长度。比如题目示例11 121 22 12 2023中。以1结尾这里的1为数字11末位的1的长度为411 121 12 2023、以2结尾这里的2为数字22末位的2的长度为222 2023、以3结尾这里的3为数字2023末位的3的长度为12023。而dp数组的作用即是存放他们对应数字的长度。如dp[1]存放的数字代表1第一次作为末位数出现的接龙数列长度。
*对于dp[b]dp[a]1dp[b]?dp[a]1:dp[b]的解释 在这个表达式中我们比较了两个值dp[a] 1和dp[b]。其中dp[a]1表示将当前数字作为最后一个数字时的最长接龙序列长度加上1即将当前数字接在前一个数字之后形成的新的接龙序列长度。而dp[b]表示当前数字作为末位数字时的已知的最长接龙序列长度。 我们通过比较这两个值的大小选择较大的值来更新dp数组中的值。如果dp[a] 1大于dp[b]则说明将当前数字接在前一个数字之后形成的新的接龙序列长度更长我们就将dp[b]更新为dp[a] 1。否则如果dp[a] 1小于等于dp[b]则说明当前数字无法接在前一个数字之后形成更长的接龙序列我们就保持dp[b]不变。 通过这样的更新操作我们可以逐步计算出每个数字作为末位数字时的最长接龙序列长度从而得到最终的结果。
————如有问题欢迎评论区提问————
