打卡记录
三个无重叠子数组的最大和
链接
滑动窗口
class Solution:def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:n, ans = len(nums), []sum1 = sum2 = sum3 = 0maxsum1idx, maxsum12idx = 0, ()maxsum1 = maxsum12 = total = 0for i in range(2 * k, n):sum1 += nums[i - 2 * k]sum2 += nums[i - k]sum3 += nums[i]if i >= 3 * k - 1:if sum1 > maxsum1:maxsum1 = sum1maxsum1idx = i - 3 * k + 1if maxsum1 + sum2 > maxsum12:maxsum12 = maxsum1 + sum2maxsum12idx = (maxsum1idx, i - 2 * k + 1)if maxsum12 + sum3 > total:total = maxsum12 + sum3ans = [*maxsum12idx, i - k + 1]sum1 -= nums[i - 3 * k + 1]sum2 -= nums[i - 2 * k + 1]sum3 -= nums[i - k + 1]return ans
动态规划 + 回溯
class Solution:def maxSumOfThreeSubarrays(self, nums, k):n = len(nums)sums = list(accumulate(nums, initial=0))dp = [[0] * 4 for _ in range(n + 10)]for i in range(n - k + 1, 0, -1):for j in range(1, 4):dp[i][j] = max(dp[i + 1][j], dp[i + k][j - 1] + sums[i + k - 1] - sums[i - 1])ans = [0] * 3i, j, idx = 1, 3, 0while j > 0:if dp[i + 1][j] > dp[i + k][j - 1] + sums[i + k - 1] - sums[i - 1]:i += 1else:ans[idx] = i - 1i += kj -= 1idx += 1return ans
T 秒后青蛙的位置（树状DP）
链接
class Solution:def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:g = [[] for _ in range(n + 1)]g[1].append(-1)for x, y in edges:g[x].append(y)g[y].append(x)ans = 0def dfs(x, fa, time, k):if x == target and (time == 0 or len(g[x]) == 1):nonlocal ansans = 1 / kreturn Trueif x == target or time == 0:return Falsefor y in g[x]:if y == fa:continueif dfs(y, x, time - 1, k * (len(g[x]) - 1)):return Truedfs(1, -1, t, 1)return ans
树上最大得分和路径（树状DP）
链接
class Solution:def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:n = len(amount)g = [[] for _ in range(n)]g[0] = [-1]for x, y in edges:g[x].append(y)g[y].append(x)Bob_times = [n] * ndef dfs1(x, fa, time):if x == 0:Bob_times[0] = timereturn Truefor y in g[x]:if y == fa:continueif dfs1(y, x, time + 1):Bob_times[x] = timereturn Truereturn Falsedfs1(bob, -1, 0)def dfs2(x, fa, time, score):if time < Bob_times[x]:score += amount[x]elif time == Bob_times[x]:score += amount[x] // 2if len(g[x]) == 1:return scoreres = -inffor y in g[x]:if y == fa:continueres = max(res, dfs2(y, x, time + 1, score))return resreturn dfs2(0, -1, 0, 0)
