广州企业做网站,做网站一个月可以赚多少钱,如何找回网站备案密码,影视公司注册流程及费用题目来源#xff1a;acwing 275 传纸条
分析#xff1a;这题和两人同时摘樱桃之类的题一样#xff0c;一个人从左上角走到右下角#xff0c;再从右下角走回左上角#xff0c;相同地点的分数只能得一次#xff08;或者不能走相同地点#xff09;。这种题统一可以按照两…题目来源acwing 275 传纸条
分析这题和两人同时摘樱桃之类的题一样一个人从左上角走到右下角再从右下角走回左上角相同地点的分数只能得一次或者不能走相同地点。这种题统一可以按照两个人从左上角一起出发走到右下角相同格子得分只能算一次来计算。
状态定义f[k][i1][i2] 代表从(0,0)出发已经走了k步两个人横坐标分别为i1,i2时得分最大值
结果f[m n][m 1][m 1] 从0走到m一共走m步从(0,0)走到(m,n) 一共要走m n步横坐标范围从0-m共m1
状态转移f[k][i1][i2] 从f[k-1]转移过来(i,j) 从(i-1,j),(i,j - 1)转移过来当i1 i2时j1j2同一个点注意只能取一次这种情况肯定小于两个点不同的情况如果分数有负数这里可以考虑加上一个负无穷所以最终答案肯定是两个人走的路径不同的更优情况。
m,n map(int,input().split())
g []
for _ in range(m):g.append(list(map(int,input().split())))f [[[0]*(m 1) for _ in range(m 1)] for _ in range(m n 1)]
for k in range(2,m n 1):for i1 in range(1,m 1):for i2 in range(1,m 1):j1,j2 k - i1,k - i2if 1 j1 n and 1 j2 n:x g[i1 - 1][j1 - 1] (g[i2 - 1][j2 - 1] if i1 ! i2 else 0)f[k][i1][i2] max(f[k - 1][i1 - 1][i2 - 1],f[k - 1][i1][i2],f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1]) x
print(f[-1][-1][-1])
类似题目https://leetcode.cn/problems/cherry-pickup/
class Solution:def cherryPickup(self, grid: List[List[int]]) - int:n len(grid)if grid[0][0] -1:return 0# 两人一起走f [[[-inf]*(n 1) for _ in range(n 1)] for _ in range(n n 1)]f[2][1][1] grid[0][0]for k in range(2,n n 1):for i1 in range(1,n 1):for i2 in range(1,n 1):if k 2 and i1 1 and i2 1:continuej1,j2 k - i1,k - i2if 1 j1 n and 1 j2 n and grid[i1 - 1][j1 - 1] 0 and grid[i2 - 1][j2 - 1] 0:x grid[i1 - 1][j1 - 1] (grid[i2 - 1][j2 - 1] if i1 ! i2 else 0)f[k][i1][i2] max(f[k - 1][i1 - 1][i2 - 1],f[k - 1][i1][i2],f[k - 1][i1 - 1][i2],f[k - 1][i1][i2 - 1]) xreturn max(f[-1][-1][-1],0)
https://leetcode.cn/problems/cherry-pickup-ii/
class Solution:def cherryPickup(self, grid: List[List[int]]) - int:m,n len(grid),len(grid[0])f [[[-inf]*n for _ in range(n)] for _ in range(m)]f[0][0][-1] grid[0][0] grid[0][-1]for i in range(1,m):for j1 in range(n):for j2 in range(n):x grid[i][j1] (grid[i][j2] if j1 ! j2 else 0)for y1 in (j1 - 1,j1,j1 1):for y2 in (j2 - 1,j2,j2 1):if 0 y1 n and 0 y2 n:f[i][j1][j2] max(f[i - 1][y1][y2] x,f[i][j1][j2])return max(f[-1][j][j1] for j in range(n) for j1 in range(n))
