HJ103 Redraiment的走法(梅花桩递增可走的最多步数)_排序_动态规划

发布时间 2023-04-05 14:36:48作者: Aneverforget

思路:

该题目符合,最优结果拥有最优子结果的特征。考虑用动态规划。通过循环获取每个参数作为最后一个桩的最优子结果,后面桩的结果为前一个桩的最优子结果+1。如梅花桩“2 5 1 5 4 5”。参考高赞答案,代码如下

 1 import sys
 2 a=int(sys.stdin.readline().strip())
 3 b=list(map(int,sys.stdin.readline().strip().split()))
 4 bp=[1 for i in range(a)]#每个梅花桩最少梅花桩步数为1,自己本身
 5 #print(bp)
 6 for i in range(a-1):#循环以i为第一步
 7     for j in range(i+1,a):#循环得到j的梅花桩步数
 8         if b[j]>b[i]:
 9             bp[j]=max(bp[j],bp[i]+1)#b[j]>b[i]则b[j]一定比b[i]大一步。
10 print(max(bp))