考虑动态规划,定义dp[i][j][0/1]表示移动到了(i,j)且第0/1个人操作完后的成本,Min即代表最小成本,Max即代表最大成本。
当从终点向起点求解时,就有向上/下、向左三种方法,根据不同的方法更新dpMin,dpMax数组即可。
给定一个2行N列的矩阵A。一个有效路径为从起点(1,1)出发,经过向上、向下或向右的移动,不重复访问同一个方格,最终到达终点(2,N)。
现在有两名玩家,他们轮流选择路径上的下一个方格(游戏从第一个玩家选择方格(1,1)开始)。当路径到达终点(2,N)时,游戏停止。
路径的成本定义为路径上所有方格上数字的总和。第一个玩家希望最大化路径的成本,而第二个玩家希望最小化路径的成本。如果两个玩家都采取最优策略,路径的成本将是多少?
第一行输入一个整数 N(1≤N≤105)表示矩阵的列数。
接下来两行,每行均包含N个整数,表示矩阵A中的元素(−105≤Aij≤105)。
输出一个整数,表示两个玩家都采取最优策略下的路径成本。
输入
3
1 5 2
3 4 0
输出
8
说明
两个玩家都采取最优策略下的路径为:1→3→4→0,路径成本为1+3+4+0=8