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

标签：Redraiment 梅花桩 range sys HJ103 bp 最优 步数

思路：

该题目符合，最优结果拥有最优子结果的特征。考虑用动态规划。通过循环获取每个参数作为最后一个桩的最优子结果，后面桩的结果为前一个桩的最优子结果+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))

 

标签：Redraiment,梅花桩,range,sys,HJ103,bp,最优,步数
From： https://www.cnblogs.com/tanyuanqing/p/17289399.html