题解(四维dp)
2024-06-02 20:00:19
发布于:上海
9阅读
0回复
0点赞
很显然这是一道dp(只能右或下,无后效性)。那么一起来分析吧!
首先倒过来想,一条路径正走和反走,它们的和都是一样的。所以我们可以把题意改成:
从左上到右下,走两条路径,不能相交(班里每个同学只会帮他们一次),只能右走或下走,求两条路径最大和。
这样,状态设置就可以直接参考这题(acgo)或这题(洛谷)了。状态转移方程也是类似的,。但是,两条路径不能相交怎么搞?很简单,把 的范围设置为 就行了。这样子,第二条路径一定在第一条路径的右上方。
注意,最后的结果应该是 ,因为 是从 开始扫的, 无意义。又因为第二条路径一定在第一条路径的右上方,所以第一条路径一定传给右下角的人左边,第一条路径一定传给右下角的人上边,那么就可以把 作为结果。
时空复杂度均为 ,可过。
本题 f 数组可以用滚动数组压掉一维,空间复杂度变成 O(n^3),不过不搞也不会MLE
温馨提示:不要复制哟。FZ,HGZF
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cmath>
using namespace std;
int f[51][51][51][51];
int a[51][51];
int main(){
int m,n;
cin >> m >> n;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
cin >> a[i][j];
}
}
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
for(int k=1; k<=m; k++){
for(int l=j+1; l<=n; l++){
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1])
max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
}
}
}
}
cout << f[m][n-1][m-1][n];
return 0;
}
这里空空如也
有帮助,赞一个