首页 > 代码库 > CodeForces 429B Working out
CodeForces 429B Working out
dp1:(1,1)到(i,j) dp2:(n,m)到(i,j) dp3:(1,m)到(i,j) dp4:(n,1)到(i,j)
因为除边界点之外所有点都有可能是相遇点 而且要使相遇仅发生一次那么单体在相遇点前的方向和后的方向相同 各自不同 只有2种可能
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <string> #define LL long long #define WW freopen("in.txt","r",stdin) #define RR freopen("out.txt","w",stdout) #define INF 0x3f3f3f3f using namespace std; const int maxn = 1010; int dp1[maxn][maxn],dp2[maxn][maxn],dp3[maxn][maxn],dp4[maxn][maxn]; int a[maxn][maxn]; int main() { int n,m; 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++) { dp1[i][j] = max(dp1[i-1][j],dp1[i][j-1]) + a[i][j]; } } for(int i=n;i>=1;i--) { for(int j=m;j>=1;j--) { dp2[i][j] = max(dp2[i+1][j],dp2[i][j+1]) + a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=m;j>=1;j--) { dp3[i][j] = a[i][j] + max(dp3[i-1][j], dp3[i][j+1]); } } for(int i=n;i>=1;i--) { for(int j=1;j<=m;j++) { dp4[i][j] = a[i][j] + max(dp4[i][j-1], dp4[i+1][j]); } } int 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+1][j]+dp3[i][j+1]+dp4[i][j-1]); ans = max(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]); } } printf("%d\n",ans); return 0; }
CodeForces 429B Working out
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。