A37462. 有一组正整数数据，现对这组数据按照如下操作：1）从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加1（例如：两个相邻的6，变成一个7）；2）重复操作第1步，直到这组数据中没有相邻且相同的数时，操作结束。现给定N（1≤N≤2000）个正整数，表示这一组数，请问按照要求操作结束后，这组数据中最大的数是多少。注意：不同的操作方式得到的最后结果不同，要求最后的结果是所有操作方式中…
填空题
困难
知识点
题目描述
题目描述：
有一组正整数数据，现对这组数据按照如下操作：
1）从这组数中找出两个相邻且相同的数，删掉其中一个数，剩下的一个数加1（例如：两个相邻的6，变成一个7）；
2）重复操作第1步，直到这组数据中没有相邻且相同的数时，操作结束。
现给定N（1≤N≤2000）个正整数，表示这一组数，请问按照要求操作结束后，这组数据中最大的数是多少。
注意：不同的操作方式得到的最后结果不同，要求最后的结果是所有操作方式中最大的。
例如：
当N=6，这组数为 1、2、2、2、3、4时，
可获得最大结果的操作如下：
第一次操作：将这组数据中后两个相邻的2，变成3，此时这组数变为1，2，3，3，4；
第二次操作：将这组数据中两个相邻的3，变成4，此时这组数变为1，2，4，4；
第三次操作：将这组数据中两个相邻的4，变成5，此时这组数变为1，2，5；
此时这组数据中没有相邻且相同的数，操作结束，最大的数是5。
非最大结果的操作如下：
第一次操作：将这组数据中前两个相邻的2，变成3，此时这组数变为1，3，2，3，4；
此时这组数据中没有相邻且相同的数，操作结束，最大的数是4。
所以按照要求操作结束后，这组数据中可获得的最大数是5。
输入描述
第一行输入一个正整数N（1≤N≤2000）
第二行输入N个正整数（1≤正整数≤40），相邻两个数之间以一个空格隔开
输出描述
输出一个正整数，表示所有操作方式中最大的结果
样例输入
6
1 2 2 2 3 4
样例输出
5
参考答案
n=int(input())
ls_a=list(map(int,input().split()))
ls_f=[[0]*(n+2) for _ in range(52)]
k=1
for i in ls_a:
ls_f[i][k]=k+1
k+=1
ans=0
for i in range(2,50):
for j in range(1,n+1):
if ls_f[i][j]==0:
ls_f[i][j]=ls_f[i-1][ls_f[i-1][j]]
if ls_f[i][j]!=0:
ans=i
print(ans)答案解析
动态规划
上一题
下一题