解题思路:
极简 线性DP-Dotcpp编程社区
dp[]数组长度设置为10,因为接龙数列的每一项均为数字,从1~9,0不需要考虑进去;
dp[]数组的含义:以i结尾的接龙数列的最大长度;
设a为接龙数列的第一个数字,b为最后一个数字;
dp[a]表示已a结尾的接龙数列的最大长度,dp[b]表示以b结尾的最大接龙数列长度
初始都是0,从0开始不断变化;
解释:假设输入5位,分别为11 121 22 12 2023;
打印dp[]数组的结果为:
0 2 3 4 0 0 0 0 0 0 #第一个0不用管,因为前导不含0
仔细推导第三、四便可以看出;
#还有些混乱,后续补充......
注意事项:
设a为接龙数列的第一个数字,b为最后一个数字;
dp[]数组的含义:以i结尾的接龙数列的最大长度;
参考代码:
N =int(input()) dp=[0 for _ in range(10)] ab = list(map(str,input().split())) for i in range(N): a,b=int(ab[i][0]),int(ab[i][-1]) dp[b] =max(dp[a]+1,dp[b])#dp[a]为上一个以a结尾的最长接龙数列长度, length = max(dp) print(N-length)
0.0分
5 人评分
P1001 (C语言代码)浏览:801 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:633 |
Cylinder (C语言描述+详细分析)浏览:3266 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:676 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:562 |
IP判断 (C语言代码)浏览:539 |
前10名 (C语言代码)浏览:727 |
简单的a+b (C语言代码)浏览:504 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:376 |
汽水瓶 (C语言代码)浏览:536 |