CodeForces - 429B Working out(dp)

CodeForces - 429B

题目

就是说有有一个人从矩阵左上角到右下角，只能向右向下走，有一个人从左下角到右上角，只能向右向上走，获得路过处的价值，期间两个人要在一个且仅一个地方碰头，不获得那个地方的价值。问两个人获得价值最大值。

思路

想到从四个角进行dp就不难了，dp就是递推，然后枚举碰头的点，注意碰头的点不能在边界（可以想想），关键是从四个角dp的思路很巧妙。

代码

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<stack> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int maxn=1010; ll dp1[maxn][maxn]; ll dp2[maxn][maxn]; ll dp3[maxn][maxn]; ll dp4[maxn][maxn]; ll ma[maxn*2][maxn*2]; int n,m; ll solve() { for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])+ma[i][j]; for(int i=1; i<=n; i++) for(int j=m; j>=1; j--) dp2[i][j]=max(dp2[i-1][j],dp2[i][j+1])+ma[i][j]; for(int i=n; i>=1; i--) for(int j=1; j<=m; j++) dp3[i][j]=max(dp3[i][j-1],dp3[i+1][j])+ma[i][j]; for(int i=n; i>=1; i--) for(int j=m; j>=1; j--) dp4[i][j]=max(dp4[i+1][j],dp4[i][j+1])+ma[i][j]; ll ans=0; for(int i=2; i<n; i++) for(int j=2; j<m; j++) { ans=max(ans,dp1[i-1][j]+dp2[i][j+1]+dp3[i][j-1]+dp4[i+1][j]); ans=max(ans,dp1[i][j-1]+dp2[i-1][j]+dp3[i+1][j]+dp4[i][j+1]); } return ans; } int main() { scanf("%d %d",&n,&m); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%I64d",&ma[i][j]); printf("%I64d\n",solve()); return 0; }