智力大冲浪 - 动态规划求解最大收益

思路：动态规划。/n/n设 $f(i,j)$ 表示在前 $i$ 个游戏中，结束时间为 $j$ 时能赢取的最多的钱。/n/n转移时考虑第 $i$ 个游戏，在 $j$ 时完成它的收益是 $m-w_i$，在 $j-1$、$j-2$、$//cdots$、$t_i$ 时完成它的收益是 $m$。则可以得到：/n/n$$f(i,j)=/max_{k=t_i}^{j-1}/{f(i-1,k)/}+m-w_i$$/n/n其中 $t_i$ 为第 $i$ 个游戏的规定完成期限。/n/n因为第 $i$ 个游戏必须在整时段内完成，所以当 $j<t_i$ 时 $f(i,j)=0$。/n/n最终答案为 $/max_{j=1}^{n}/{f(n,j)/}$。/n/n时间复杂度 $O(n^3)$。/n/n代码：/n/npython/n# 输入/nm = int(input())/nn = int(input())/nt = list(map(int, input().split()))/nw = list(map(int, input().split()))/n/n# 初始化 dp 数组/ndp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]/n/n# 动态规划/nfor i in range(1, n + 1):/n for j in range(t[i - 1], n + 1):/n dp[i][j] = max(dp[i - 1][k] for k in range(t[i - 1], j)) + m - w[i - 1]/n/n# 输出最大收益/nprint(max(dp[n]))/n