一、走两次行不行
这是一种类似贪心的解法,第一次选择最大的,然后把最大路径上的数字都置为空,第二次再选择最大的。
这就是[HTML_REMOVED][HTML_REMOVED]只见树木不见森林[HTML_REMOVED][HTML_REMOVED]的方法:
第一次走为局部最优并且也对第二次走造成了影响,第二次走是在第一次影响下所能走的局部最优,不具备无后效性,因此分开两次走并不是全局最优解。
举一个反例来证明,
9 0 3
0 9 2
0 2 0
最长路径是$9+9+2=20$,假设这次走的路线是第一行的$9$、第二行的$9$和$2$,那么在第二次走的时候,地图变成
0 0 3
0 0 0
0 2 0
显然最长路径是$3$,总和为$23$。
然而这不是最优解,最优解是第一次走第一行的$9$、第二行的$9$、第三行的$2$(仍是$20$),但第二次可以走第一行的$3$、第二行的$2$,得到$5$,总和达到$25$。
打个比方吧,以我熟悉的篮球比赛为例子,假设现在中国篮协选了杜峰和李楠两个人同时成为主教练(好奇葩的作法,是吧~),他们一起执教同一场对澳大利亚的比赛:
-
方案$1$:杜锋执教上半场,只关注上半场局势,不关心下半场。李楠执教下半场,只关注下半场局势,不关心上半场。结果,上半场往死了打,每个球员犯规$5$次,体力用尽,上半场比分与澳大利亚打平。可是到了下半场,球员都无法上场了,也没劲了,只能一节得$3$分,被羞辱~,为什么会这样呢?因为需要整体考虑,根据自身情况,制订合理战术,该节约体能需要节约,要控制犯规,最后一节好好冲刺,就可以与袋鼠一战,可因为两个教练互相独立,不关心另一半,当然不会考虑这些,只保证自己好就行了,最终的整体结果当然不一定是最好的。
-
方案$2$:两人能力合作,权衡全场,该攻就攻,该守就守,合理分配体能,不过早的暴露攻击点,最后关键时刻给敌人致命一击,成功拿下比赛,最终结果最重要,国家荣誉最重要。
很明显,傻子都知道方案$2$是最优选择。
两个小朋友一起走为什么就行呢?因为他们在一起整体考虑,互相关心互相照顾~,彼此能知道对方走了哪个点,自己在不影响最优取值的情况下,尽可能的取次优的点,这样,就可以得到全局最优解。
二、四维状态解法
四维的状态表示$f[x_1][y_1][x_2][y_2]$的含义是很明显的,就是两个小朋友分别在$(x_1,y_1)$,$(x_2,y_2)$的状态下,此时的最优解是多少。
它的前序状态应该是
$$
\large \left\{\begin{matrix}
f(x_1-1,y_1)& f(x_2-1,y_2) & 下下 \\
f(x_1-1,y_1)& f(x_2,y_2-1) & 下右 \\
f(x_1,y_1-1)& f(x_2-1,y_2) & 右下\\
f(x_1,y_1-1)& f(x_2,y_2-1) & 右右
\end{matrix}\right.
$$
这四种情况,都有可能成为$f[x_1][y_1][x_2][y_2]$的前序,具体走哪个,需要对四个进行求$max$,谁大取谁。
int t = f[x1 - 1][y1][x2 - 1][y2]; //下下
t = max(t, f[x1][y1 - 1][x2][y2 - 1]); //右右
t = max(t, f[x1 - 1][y1][x2][y2 - 1]); //下右
t = max(t, f[x1][y1 - 1][x2 - 1][y2]); //右下
还有一个问题没有解决,就是,没有加上当前状态新到的位置上的数字,这个需要讨论一下:
-
两个小朋友走的格子不是同一个
$w=t+w[x_1][y_1]+w[x_2][y_2]$ -
两个小朋友走的格子是同一个
因为题目要求每个格子只能取一次,就是说如果同一时间走到同一个格子中,应该是取一次值即可。
$w=t+w[x_1][y_1]$
利用四层循环,从上到下,从左到右的完成状态表的填充,就可以取得正确答案:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n; //方格的宽度和高度
int w[N][N]; //每个方格里面的数字
int f[N][N][N][N]; //四维的DP数组
int main() {
scanf("%d", &n);
//接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
int a, b, c;
//一行 0 0 0 表示结束。
while (scanf("%d %d %d", &a, &b, &c), a || b || c) w[a][b] = c;
//开始递推
for (int x1 = 1; x1 <= n; x1++)
for (int y1 = 1; y1 <= n; y1++)
for (int x2 = 1; x2 <= n; x2++)
for (int y2 = 1; y2 <= n; y2++) {
if (x1 == x2 == y1 == y2 == 1)
f[1][1][1][1] = w[1][1];
else if (x1 + y1 == x2 + y2) {
int t = f[x1 - 1][y1][x2 - 1][y2]; //下下
t = max(t, f[x1][y1 - 1][x2][y2 - 1]); //右右
t = max(t, f[x1 - 1][y1][x2][y2 - 1]); //下右
t = max(t, f[x1][y1 - 1][x2 - 1][y2]); //右下
//加上这个点的数值
f[x1][y1][x2][y2] = t + w[x1][y1];
//如果这个点没有被重复走,那么再加一次
if (x1 != x2 && y1 != y2) f[x1][y1][x2][y2] += w[x2][y2];
}
}
printf("%d", f[n][n][n][n]);
return 0;
}
三、四维状态优化版本
上面四维的写法,就足以$AC$掉这道题了,但是在时间上还是可以优化的。原因是使用瞪眼大法仔细看,明白上面的递推关系式中,$(x_1,y_1)$与$(x_2,y_2)$其实是有关系的,刚才我们把关系写在了四层循环的内侧,这样其实有很多情况是无效的枚举,我们只关心$x_1+y_1=x_2+y_2$的情况,所以可以利用这个关系式,减少一层循环:
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n; //方格的宽度和高度
int w[N][N]; //每个方格里面的数字
int f[N][N][N][N]; //四维的DP数组
int main() {
scanf("%d", &n);
//接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
int a, b, c;
//一行 0 0 0 表示结束。
while (scanf("%d %d %d", &a, &b, &c), a || b || c) w[a][b] = c;
//开始递推
for (int x1 = 1; x1 <= n; x1++)
for (int y1 = 1; y1 <= n; y1++)
for (int x2 = 1; x2 <= n; x2++) {
int y2 = x1 + y1 - x2; //通过计算可以减少一维循环
if (x1 == x2 == y1 == y2 == 1)
f[1][1][1][1] = w[1][1];
else if (y2 >= 1 && y2 <= n) { //要小心点,别整出一个不符合实际情况的数
//上一个状态
int t = f[x1 - 1][y1][x2 - 1][y2];
t = max(t, f[x1][y1 - 1][x2][y2 - 1]);
t = max(t, f[x1 - 1][y1][x2][y2 - 1]);
t = max(t, f[x1][y1 - 1][x2 - 1][y2]);
//加上这个点的数值
f[x1][y1][x2][y2] = t + w[x1][y1];
//如果这个点没有被重复走,那么再加一次
if (x1 != x2 && y1 != y2) f[x1][y1][x2][y2] += w[x2][y2];
}
}
printf("%d", f[n][n][n][n]);
return 0;
}
四、三维状态版本
既然刚才想到了利用两者的坐标关系和来实现少写一层循环,那可不可以基于这一点深挖一下,获取更大的利益呢?答案是可以的,我们可以重新定义状态:
$$\large f[k][x_1][x_2]$$
其中$k$是指$x_1+y_1$的坐标和,当$k$和$x_1$确定时,$k-x_1$就是$y_1$; 当$k$和$x_2$确定时,$k-x_2$就是$y_2$;这样的话,就可以在空间上减小为三维表示法!
下面来思考一下起点和终点的情况:
- 起点:$(1,1)$是两个小朋友的出发点,所以$f[2][1][1]$是起点状态值,初始值是$w[1][1]$
- 终点:$(n,n)$是两个小朋友的终点,所以$f[2*n][n][n]$是终点状态值,也就是答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main() {
scanf("%d", &n);
//接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
int a, b, c;
//一行 0 0 0 表示结束。
while (scanf("%d %d %d", &a, &b, &c), a || b || c) w[a][b] = c;
// k表示两个小朋友所在位置的x+y的和,最多是2*n
for (int k = 2; k <= 2 * n; k++)
for (int x1 = 1; x1 <= n; x1++)//第一个小朋友竖着走的距离
for (int x2 = 1; x2 <= n; x2++) {//第二个小朋友竖着走的距离
int y1 = k - x1, y2 = k - x2;//计算横着走的距离
if (x1 == x2 == y1 == y2 == 1)
f[2][1][1] = w[1][1];
else
//不能出界,只走有效的位置
if (y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n) {
// PK获取到最优的上一个状态
int t = f[k - 1][x1 - 1][x2];
t = max(t, f[k - 1][x1 - 1][x2 - 1]);
t = max(t, f[k - 1][x1][x2 - 1]);
t = max(t, f[k - 1][x1][x2]);
//将本位置的数值加上
f[k][x1][x2] = t + w[x1][y1];
//如果不是重复的位置,还可以继续加上
if (x1 != x2 && y1 != y2) f[k][x1][x2] += w[x2][y2];
}
}
//输出DP的结果
printf("%d\n", f[2 * n][n][n]);
return 0;
}