P7074 [CSP-J 2020] 方格取数
如果设 \(f_{i,j}\) 为 \((1,1)\) 到 \((i,j)\) 的最大权值和，上下相邻的两个元素的转移就是双向的了。有后效性，无法 DP。
不过题目说“不能重复经过已经走过的方格”，也就是说每一列只能往一个方向走。
所以可以加一维规定转移方向：\(f_{i,j,k=0/1}\)，\(k=0\) 为从下面转移过来，\(k=1\) 为从上面转移过来。
这样 \(f_{i,j,0},f_{i,j,1}\) 的转移就没有后效性了：
\[\large
\begin{cases}
f_{i,j,0}=\max(f_{i+1,j,0},f_{i,j-1,0},f_{i,j-1,1})\\
f_{i,j,1}=\max(f_{i-1,j,1},f_{i,j-1,0},f_{i,j-1,1})
\end{cases}
\]
时间复杂度 \(O(nm)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+2;
int n,m,a[N][N],f[N][N][2];
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}memset(f,-0x3f,sizeof f);f[1][1][0]=f[1][1][1]=a[1][1];for(int i=2;i<=n;i++) f[i][1][1]=f[i-1][1][1]+a[i][1];for(int i=2;i<=m;i++){for(int j=1;j<=n;j++){f[j][i][1]=max({f[j-1][i][1],f[j][i-1][0],f[j][i-1][1]})+a[j][i];}for(int j=n;j>=1;j--){f[j][i][0]=max({f[j+1][i][0],f[j][i-1][0],f[j][i-1][1]})+a[j][i];}}cout<<f[n][m][1]<<"\n";return 0;
}
或者写记搜：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+2,inf=1e15;
int n,m,a[N][N],f[N][N][2];
inline int dfs(int x,int y,bool d){if(x<1||x>n||y<1||y>m) return -inf;if(f[x][y][d]^(-inf)) return f[x][y][d];if(d) f[x][y][d]=max({dfs(x-1,y,1),dfs(x,y-1,0),dfs(x,y-1,1)});else f[x][y][d]=max({dfs(x+1,y,0),dfs(x,y-1,0),dfs(x,y-1,1)});f[x][y][d]+=a[x][y];return f[x][y][d];
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];f[i][j][0]=f[i][j][1]=-inf;}}f[1][1][0]=f[1][1][1]=a[1][1];cout<<dfs(n,m,1)<<"\n";return 0;
}