首页 > 代码库 > Codeforces_429_B
Codeforces_429_B
http://codeforces.com/problemset/problem/429/B
挺简单的题,先求出四个点到每一点的最大和,然后枚举每一点,取和最大值。
注意两条路相交的点有且只有一个,这点的数值不加。
#include<iostream>#include<algorithm>using namespace std;int a[1005][1005];int s1[1005][1005] = {0},e1[1005][1005] = {0},s2[1005][1005] = {0},e2[1005][1005] = {0};int main(){ int n,m; cin >> n >> m; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) cin >> a[i][j]; } s1[1][1] = a[1][1]; s2[n][1] = a[n][1]; e1[n][m] = a[n][m]; e2[1][m] = a[1][m]; for(int i = 2;i <= n;i++) { s1[i][1] += a[i][1]+s1[i-1][1]; e2[i][m] += a[i][m]+e2[i-1][m]; } for(int i = n-1;i >= 1;i--) { s2[i][1] += a[i][1]+s2[i+1][1]; e1[i][m] += a[i][m]+e1[i+1][m]; } for(int i = 2;i <= m;i++) { s1[1][i] += a[1][i]+s1[1][i-1]; s2[n][i] += a[n][i]+s2[n][i-1]; } for(int i = m-1;i >= 1;i--) { e2[1][i] += a[1][i]+e2[1][i+1]; e1[n][i] += a[n][i]+e1[n][i+1]; } for(int i = 2;i <= n;i++) { for(int j = 2;j <= m;j++) { s1[i][j] = max(s1[i-1][j]+a[i][j],s1[i][j-1]+a[i][j]); } for(int j = m-1;j >= 1;j--) { e2[i][j] = max(e2[i-1][j]+a[i][j],e2[i][j+1]+a[i][j]); } } for(int i = n-1;i >= 1;i--) { for(int j = 2;j <= m;j++) { s2[i][j] = max(s2[i][j-1]+a[i][j],s2[i+1][j]+a[i][j]); } for(int j = m-1;j >= 1;j--) { e1[i][j] = max(e1[i][j+1]+a[i][j],e1[i+1][j]+a[i][j]); } } int ans = 0; for(int i = 2;i < n;i++) { for(int j = 2;j < m;j++) { ans = max(ans,s1[i-1][j]+s2[i][j-1]+e1[i+1][j]+e2[i][j+1]); ans = max(ans,s1[i][j-1]+s2[i+1][j]+e1[i][j+1]+e2[i-1][j]); } } cout << ans << endl; return 0;}
Codeforces_429_B
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。