两个一起走,只能用两个四层循环走罢
~~我也不确定啊~~
by Guo1 @ 2023-07-31 11:15:50
@[lpx2023](/user/537998)
题目中明确说了
```
此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大
```
第一次走的最优解并不一定能使两次走的值最大
给你这个数据
```
0 0 2 3 0 0 0
0 0 3 0 0 0 0
0 0 3 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 4 0 0
0 0 0 0 4 0 0
0 0 2 0 4 0 0
```
第一次走
```
0 0 0 0 0 0 0
0 0 3 0 0 0 0
0 0 3 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 2 0 0 0 0
```
第二次取完
如果按照你说的每一次都是最优解,第一次走
```
0 0 0 3 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 2 0 0 0 0
```
那么你最后会剩一个2没有取走。
而通过观察可以发现,是有方法两次取走所有数的
~~求关~~
by 大海中的孤帆 @ 2023-08-04 15:59:41
不对啊,我说的意思是让两个点同时走,每一轮走1和2中最优的
by lpx2024 @ 2023-08-11 18:59:55
@[lpx2023](/user/537998) 因为第一次最优的路线不止一条,导致可能第二条不一定是最大的,要把所有最优的路径全部列举一边才能找到真正的第二条路径的最大值,你可以去看看我昨天发的讨论,那里我讲了个例子
by zenglx @ 2023-08-24 11:42:55
其实按上面那代码或题解的写法,f[i][j][k][l]就不能表示第一遍走到点(i,j),第二遍走到点(k,l)的最优解,或者说只有在i==k且j==l时才成立。例:
```cpp
//输入
3
2 2 5
3 3 10
0 0 0
//按这个输入后表格的数则为:
0 0 0
0 5 0
0 0 10
```
然后我们尝试输出f[3][3][2][2]的值会发现它为等于20,明显不符合我们的定义。
每次状态转移时同时走,可以使两人步数相同,很巧合地使i==k且j==l时,f[i][j][k][l]刚好为最优解。(我个人目前认为4维dp的那种解法有点瞎猫碰见死耗子的感觉)lz一步一步走的想法是基于f[i][j][k][l]就表示第一遍走到点(i,j),第二遍走到点(k,l)的最优解,但这样会导致后效性的出现。
by 荔_冰淇淋 @ 2024-02-18 19:52:06