题目链接戳这里
给n*m的矩阵,每个格子有一个值,A从(1,1)出发只能向下或右走,终点为(n,m),B从(n,1)出发只能向上或右走,终点为(1,m)。一次走一步。走到的格子可以获的该格子的数,两人同时走的格子数值不算入各自的和。求A和B能拿到的数的总和的最大值。
思路:dp+枚举。
先利用dp获得所有可能的路线(后细说)的最大值,然后枚举所有相遇地点,取各种路线的max为答案。
dp1[i][j],A从(1,1)到(i,j)的max和
dp2[i][j],A从(i,j)到(n,m)的max和
dp3[i][j],B从(n,1)到(i,j)的max和
dp4[i][j],B从(i,j)到(1,m)的max和。
留意求的时候,比如dp2,for循环要逆向的从(n,m)开始回推。
最后,相遇的情况有两种,第一种是A往右,B往上,相遇,A和B保持方向不变形成交叉。第二种A往下,B往右,相遇,A和B保持方向不变形成交叉。枚举每个相遇点别忘记有这2种情况。
于是最终代码:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
const int inf = 0x3f3f3f3f, maxN = 1e3 + 5;
int N, M, T;
int dp1[maxN][maxN], dp2[maxN][maxN];
int dp3[maxN][maxN], dp4[maxN][maxN];
int a[maxN][maxN];
int main() {
scanf("%d%d", &N, &M);
rep(i, 1, N + 1)
rep(j, 1, M + 1)
scanf("%d", &a[i][j]);
rep(i, 1, N + 1)
rep(j, 1, M + 1)
dp1[i][j] = a[i][j] + max(dp1[i - 1][j], dp1[i][j - 1]);
rrep(i, 1, N + 1)
rrep(j, 1, M + 1)
dp2[i][j] = a[i][j] + max(dp2[i][j + 1], dp2[i + 1][j]);
rrep(i, 1, N + 1)
rep(j, 1, M + 1)
dp3[i][j] = a[i][j] + max(dp3[i][j - 1], dp3[i + 1][j]);
rep(i, 1, N + 1)
rrep(j, 1, M + 1)
dp4[i][j] = a[i][j] + max(dp4[i - 1][j], dp4[i][j + 1]);
int ans = 0;
rep(i, 2, N) {
rep(j, 2, M) {
ans = max(ans, dp1[i][j - 1] + dp2[i][j + 1] + dp3[i + 1][j] + dp4[i - 1][j]);
ans = max(ans, dp1[i - 1][j] + dp2[i + 1][j] + dp3[i][j - 1] + dp4[i][j + 1]);
}
}
printf("%d\n", ans);
return 0;
}
网友评论