<-养成先点赞后阅读的好习惯(逃
宣传一下 算法提高课整理,欢迎踩爆。
时间较长做法(1170ms)
时间较长 AC 较为简单,可以参考一下我的一篇题解 方格取数,把代码搬过来改一下输入和N就行了。
时间较长Code:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int ma[N][N][N][N], a[N][N], n, m, x;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ ) scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
for(int k = 1; k <= n; k ++ )
for(int l = 1; l <= m; l ++ ){
ma[i][j][k][l] = max({ma[i-1][j][k-1][l],ma[i-1][j][k][l-1], ma[i][j-1][k-1][l],ma[i][j-1][k][l-1]}) + a[i][j] + a[k][l];
if(i == k && j == l) ma[i][j][k][l] -= a[i][j];
}
printf("%d\n", ma[n][m][n][m]);
return 0;
}
正解思路(32ms)
状态表示:f[k, i, j]
表示两个人同时走了 $k$ 步,第一个人在 $(i, k - i)$ 处,第二个人在 $(j, k - j)$ 处的所有走法的最大花费。
考虑状态转移:
$\;\;\;\;\;\;\;$两个人同时向右走,最大分值是 f[k - 1, i, j] + score(k, i, j)
$\;\;\;\;\;\;\;$第一个人向右走,第二个人向下走,最大分值是 f[k - 1, i, j - 1] + score(k, i, j)
$\;\;\;\;\;\;\;$第一个人向下走,第二个人向右走,最大分值是 f[k - 1, i - 1, j] + score(k, i, j)
$\;\;\;\;\;\;\;$两个人同时向下走,最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)
;
注:此为 y 总的思路,为转载。
所以代码也就呼之欲出了hh。
Code:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int f[N * 2][N][N], a[N][N], n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ ) scanf("%d", &a[i][j]);
for(int i = 1; i <= n+m; i ++ )
for(int j = 1; j <= n; j ++ )
for(int k = 1; k <= n; k ++ ){
int jy = i - j, ky = i - k;
if(jy >= 1 && jy <= m && ky >= 1 && ky <= m){
int x = a[j][jy];
if(k != j) x += a[k][ky];
int &res = f[i][j][k];
res = max(res, f[i-1][j][k]+x);
res = max(res, f[i-1][j-1][k] + x);
res = max(res, f[i-1][j-1][k-1] + x);
res = max(res, f[i-1][j][k-1] + x);
}
}
printf("%d\n", f[n+m][n][n]);
return 0;
}
大佬您好!请问4维dp的那种写法,为什么让l和k倒过来,从m和n开始遍历,然后减减,最后输出ma[m][n][1][1]是不行的呢?
这是我的代码
为什么要倒着枚举捏
hh其实就是想起来这个题纸条还要倒着传回去,那么有一条路线从[m,n]传回了[1,1],另外一条是从[1,1]传到[m,n]但是这样写最后不太对qwq
那我也不知道qwq,我是蒟蒻,不是佬/kk
利用未被计算的状态进行更新
谢佬qwq/bx