算法1
(三维DP) $O(n^3)$
把 $f[i1][j1][i2][j2]$ 转化为 $f[k][i1][i2]$
其中 $k == i1 + j1 == i2 + j2$
等价于 $ f[i1][k-i1][i2][k-i2] $
这样在处理 两次走到相同点的时候,可以转化为
$i1 == i2$ 或者 $j1 == j2$ 判断其中之一即可
由$f[i1][j1-1][i2][j2-1]$ 转化为$ f[k-1][i1][i2]$
因为 $ k-1 == i1 + j1 - 1 == i2 + j2 - 1$
同理可得
$f[i1-1][j1][i2-1][j2] == f[k-1][i1-1][i2-1] $
$f[i1][j1-1][i2-1][j2] == f[k-1][i1][i2-1] $
$f[i1-1][j1][i2][j2-1] == f[k-1][i1-1][i2] $
注意 $ k $的范围 $2 - n + n$,因为 刚开始的时候$ k == i1 + j1 == 2$
j1 和 j2 要判断范围 ,因为 他们是从 k转化过来的,不能超过地图的边界范围
判断 两次取同一个格子的时候 满足以下条件
$k == k$
$i1 == i2$
因此 $j1 == k - i1 == j2 == k - i2,w[i1][j2] == w[i2][j2]$
时间复杂度
$O(n^3)$
参考文献
算法提高课 DP 第一讲
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int w[N][N],f[N*2][N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n ,x,y,z;
cin >> n;
while(cin >> x >> y >> z,x && y && z) w[x][y] = z;
for(int k = 2;k <= n + n; ++k){
for(int i1 = 1;i1 <= n; ++i1){
for(int i2 = 1;i2 <= n; ++i2){
int j1 = k - i1 , j2 = k - i2;
if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x , f[k-1][i1-1][i2-1] + t);
x = max(x , f[k-1][i1-1][i2] + t);
x = max(x , f[k-1][i1][i2-1] + t);
x = max(x , f[k-1][i1][i2] + t);
}
}
}
}
cout << f[n+n][n][n] << endl;
return 0;
}
为什么用二维表示,模拟走两次会样例过了,但是wa了啊
样例过了并不代表能ac啊!
如果遇到两次能把所有点都踩到的情况:
但由于第一次和第二次没有联系,第一次只取最优解,可能会导致第二次不能把剩下的点都踩到。
1 3 2
1 4 3
2 3 3
3 3 3
5 5 4
6 5 4
7 3 2
7 5 4
这题贪心是错的,局部最优不代表全局最优
这是一种类似贪心的解法,第一次选择最大的,然后把最大路径上的数字都置为空,第二次再选择最大的。
这就是[HTML_REMOVED][HTML_REMOVED]只见树木不见森林[HTML_REMOVED][HTML_REMOVED]的方法:
第一次走为局部最优并且也对第二次走造成了影响,第二次走是在第一次影响下所能走的局部最优,不具备无后效性,因此分开两次走并不是全局最优解。
举一个反例来证明,
最长路径是$9+9+2=20$,假设这次走的路线是第一行的$9$、第二行的$9$和$2$,那么在第二次走的时候,地图变成
显然最长路径是$3$,总和为$23$。
然而这不是最优解,最优解是第一次走第一行的$9$、第二行的$9$、第三行的$2$(仍是$20$),但第二次可以走第一行的$3$、第二行的$2$,得到$5$,总和达到$25$。
打个比方吧,以我熟悉的篮球比赛为例子,假设现在中国篮协选了杜峰和李楠两个人同时成为主教练(好奇葩的作法,是吧~),他们一起执教同一场对澳大利亚的比赛:
方案$1$:杜锋执教上半场,只关注上半场局势,不关心下半场。李楠执教下半场,只关注下半场局势,不关心上半场。结果,上半场往死了打,每个球员犯规$5$次,体力用尽,上半场比分与澳大利亚打平。可是到了下半场,球员都无法上场了,也没劲了,只能一节得$3$分,被羞辱~,为什么会这样呢?因为需要整体考虑,根据自身情况,制订合理战术,该节约体能需要节约,要控制犯规,最后一节好好冲刺,就可以与袋鼠一战,可因为两个教练互相独立,不关心另一半,当然不会考虑这些,只保证自己好就行了,最终的整体结果当然不一定是最好的。
方案$2$:两人能力合作,权衡全场,该攻就攻,该守就守,合理分配体能,不过早的暴露攻击点,最后关键时刻给敌人致命一击,成功拿下比赛,最终结果最重要,国家荣誉最重要。
很明显,傻子都知道方案$2$是最优选择。
两个小朋友一起走为什么就行呢?因为他们在一起整体考虑,互相关心互相照顾~,彼此能知道对方走了哪个点,自己在不影响最优取值的情况下,尽可能的取次优的点,这样,就可以得到全局最优解。
明白了,谢谢大佬
这样四维变三维真的妙啊,妙妙妙
冒个泡
哇,大佬是👦还是👧啊
。。。
男生
卧槽 真的强 我想了半天懂
pdx
k的范围是 2n-1步,摘花生和最低通行费里面,到达最后一个格子,需要的总步数始终是 2n -1; 即表示两条路径同时在最后一个格子结束时,走了 2n-1步
确实应该是2n-1步,那是代码改成那个范围就过不去了
我刚刚又去看了一遍y总的视频,k的范围确实应该是2-2n,不是2-2n-1,如果是2-2n-1应该是下标从0开始的情况,k的范围为[2,2n], 2n-2+1=2n-1,不就正好走了2n-1步吗,它这儿的k并不是直接代表我所有的步数,而是所走到格子的横纵坐标之和。
hh
hh
写得很好