A25679. 移动小球编程实现n 个小球从左到右排成一排，每个小球上都标有一个数值。接下来进行若干次操作，每次从以下操作中任选一项：（1）移走一个小球，本次操作获得 1 积分；（2）移走 k（k≥2）个小球，要求 k 个小球上的数值相同且位置连续，本次操作获得 k×k 的积分。注：每次小球被移走后，剩余小球相对顺序不变，从左到右重新排成一排。给定 n 个小球从左到右的数值，请计算将这 n 个小球全部移走后可获…
填空题
中等
知识点
题目描述
移动小球
编程实现
n 个小球从左到右排成一排，每个小球上都标有一个数值。接下来进行若干次操作，每次从以下操作中任选一项：
（1）移走一个小球，本次操作获得 1 积分；
（2）移走 k（k≥2）个小球，要求 k 个小球上的数值相同且位置连续，本次操作获得 k×k 的积分。
注：每次小球被移走后，剩余小球相对顺序不变，从左到右重新排成一排。
给定 n 个小球从左到右的数值，请计算将这 n 个小球全部移走后可获得的总积分的最大值。
例如：n = 5；5 个小球从左到右的数值依次为 1、1、4、1、5；可按以下操作移走小球：
第一次：将 1、1、4、1、5 中数值为 4 的小球移走，剩余小球排列为 1、1、1、5，本次操作获得 1 积分；
第二次：将 1、1、1、5 中数值为 1 的 3 个小球移走，剩余小球排列为 5，本次操作获得 9（3×3）积分；
第三次：将数值为 5 的小球移走，本次操作获得 1 积分；
最终获得的总积分的最大值为 11（1 + 9 + 1）。
输入描述
第一行输入一个整数 n（1≤n≤100），表示小球的数量；
第二行输入 n 个整数（1≤整数≤100），表示从左到右每个小球的数值，整数之间以一个空格隔开。
输出描述
输出一个整数，表示总积分的最大值。
样例输入
5
1 1 4 1 5样例输出
11参考答案
n = int(input().strip())
a = list(map(int, input().split()))
dp = [[[-1] * (n + 1) for _ in range(n)] for __ in range(n)]
def solve(i, j, k):
if i > j:
return 0
if dp[i][j][k] != -1:
return dp[i][j][k]
res = (k + 1) ** 2 + solve(i, j - 1, 0)
for m in range(i, j):
if a[m] == a[j]:
res = max(res, solve(i, m, k + 1) + solve(m + 1, j - 1, 0))
dp[i][j][k] = res
return res
ans = solve(0, n - 1, 0)
print(ans)
上一题
下一题