投递深信服等公司10个岗位 >
0 点赞 评论 收藏
分享
投递第四范式等公司10个岗位 >
0 点赞 评论 收藏
分享
投递小米集团等公司10个岗位 >
0 点赞 评论 收藏
分享
投递vivo等公司10个岗位 >
0 点赞 评论 收藏
分享
投递哔哩哔哩等公司10个岗位 >
0 点赞 评论 收藏
分享
投递哔哩哔哩等公司10个岗位 >
0 点赞 评论 收藏
分享
投递华为等公司10个岗位 >
0 点赞 评论 收藏
分享
yyBeta:第四题贴个代码,做法没问题,python没有gc所以一直内存超限。。优化了很久把dp的dict改成反复清空的一维list还是不行,十分郁闷。。 其实思路跟leetcode813.最大平均值和的分组差不多,就是把平均数换成了类别数 import sys
def largestScore(A: list, K: int) -> float:
n = len(A)
count = {} # 先计算各个段的场次数方便后面调用
for i in range(n):
now = {A[i]}
count[i, i+1] = 1
for j in range(i+1, n):
now.add(A[j])
count[i, j+1] = len(now)
dp = {(1, i): count[0, i] for i in range(1, n+1)} # dp[k, i] 前i个数分成k组的最大分数
for i in range(2, n+1):
for j in range(i, n+1):
_max = dp[i-1, j-1] + 1
for k in range(i-1, j-1):
_max = max(_max, dp[i-1, k] + count[k, j])
dp[i, j] = _max
return dp[K, n]
_, K = map(int, sys.stdin.readline().strip().split(' '))
A = list(map(int, sys.stdin.readline().strip().split(' ')))
print(largestScore(A, K))
投递hulu等公司10个岗位 >
0 点赞 评论 收藏
分享
投递滴滴等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: