多多读书¶

def dp_solver(line1, line2):
    n, m = map(int, line1.split())
    a = list(map(int, line2.split()))

    # dp[i][j] 表示读完第 i 页，用了 j 时间，获得的最大知识
    dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
    # 初始状态
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 尝试读一页
            if dp[i - 1][j - 1] != -1:
                dp[i][j] = max(
                    dp[i][j], 
                    dp[i - 1][j - 1] + a[i - 1]
                )
            # 尝试读两页
            if i > 1 and dp[i - 2][j - 1] != -1:
                dp[i][j] = max(
                    dp[i][j], 
                    dp[i - 2][j - 1] + (a[i - 2] + a[i - 1]) / 2
                )
    return dp[n][m]

def dfs_solver(line1, line2):
    n, m = map(int, line1.split())
    a = list(map(int, line2.split()))

    # 记忆优化
    # mp[(idx, m)] 表示从idx开始读，有m分钟，能获得的最大知识
    mp = {}

    def dfs(idx, m):
        # idx: 下一个要读的页码
        # m: 剩余时间
        if (idx, m) in mp:
            return mp[(idx, m)]
        # 如果剩余时间不够读完
        if n - idx > 2 * m:
            return -1
        # 递归出口
        if idx == n:
            return 0
        ans = 0
        # 读一页
        res = dfs(idx + 1, m - 1)
        if res != -1:
            # 这次读一页，可以读完整本
            ans += res + a[idx]
        # 读两页
        if idx + 1 < n:
            res = dfs(idx + 2, m - 1)
            if res != -1:
                ans2 = res + (a[idx] + a[idx + 1]) / 2
                ans = max(ans, ans2)
        mp[(idx, m)] = ans
        return mp[(idx, m)]

    return dfs(0, m)