坐标问题 3

⑤ 传送门#2 到达点(a,b)后，便立刻跳转到(a',b')，反过来也能跳转，其中 a＜a'，b'＞b（否则会发生无限传送）。

解决方法：分三种情况讨论，即不经过传送门、先经过左侧的传送门、先经过右侧的传送门。

1 5 9 1 3 8 2 8 6 4 2 -∞ 7 3 7 2 5 1 9 1 6 1 0 -∞ 8 2 4 3 3 2 7 5 1 6 4 0 5 8 3 4 5 1

1 5 9 1 3 8 2 1 5 9 1 3 8 2 8 6 4 2 5 7 3 8 6 4 2 5 7 3 7 2 5 1 9 1 6 7 2 5 1 9 1 6 1 0 1 8 2 4 3 1 0 1 8 2 4 3 3 2 7 5 1 6 4 3 2 7 5 1 6 4 0 5 8 3 4 5 1 0 5 8 3 4 5 1

不经过传送门  先进入左侧的传送门  先进入右侧的传送门

(3) 传纸条

【问题简述】一个 m×n 的方格，每个格子都有一个数字，但左上角和右下角都是0。现在从方格的左上角引出两条路径，它们同时出发，都到右下角停止。要求只能往右走或往下走，一次只能走一步，且两条路径不能交叉、重合。现在使经过的所有数字的和最大，问最大值是多少？（1≤m,n≤50）

【分析】

如果还使用(1)的动态转移方程，就很有可能在第一条路径选择完成后，第二条路径无法到达终点！所以要同时考虑两条路径。

思路1：

1. 划分阶段：每走一步为一个阶段（一次只移动一张纸条）。

2. 状态表示：设两张纸条分别位于第 r1行第 c1列、第 r2行第 c2列，那么 f(r1,c1,r2,c2)表示两张纸条从起点出发，分别到达这两个点时经过的数字和的最大值。

为了保证道路不交叉，应有 x1＜r2。

f(r1－1,c1,r2,c2)＋map(r1,c1) （↓×）

ì

3. 状态转移方程：f(r1,c1,r2,c2)＝maxíff((rr11,,cc11－,r12－,r12,,cc22))＋＋mapmap((rr12,,cc12))  （（→××↓））

îf(r1,c1,r2,c2－1)＋map(r2,c2) （×→）

4. 一个优化：因为 r1＋c1＝r2＋c2，所以可以去掉一维。这样时间可由四次方降到三次方。

5. 输出：f(m, n-1, m-1, n)