題目鏈接

題意

給一個矩陣每個位置一個value，求從左上角到右下角和左下角到右上角value和，相交的地方value不計，問和最大多少

AC

• 分別求出每個點四個方向的value和
• 每個點可以有四種走法，滿足情況的只有兩種（可畫圖模擬）

#include <bits/stdc++.h> #define ll long long #define N 100005 #define mem(a, b) memset(a, b, sizeof(a)) #define P pair<int, int> using namespace std; int dp[1005][1005][4]; int a[1005][1005]; int main() {// freopen("in.txt", "r", stdin);int r, c;while(cin >> r >> c) {mem(dp, 0);for (int i = 1; i <= r; ++i) {for (int j = 1; j <= c; ++j) {cin >> a[i][j];}}for (int i = 1; i <= r; ++i) {// 右下for (int j = 1; j <= c; ++j) {dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) + a[i][j];}// 左下for (int j = c; j >= 1; --j) {dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j + 1][1]) + a[i][j];}}for (int i = r; i >= 1; --i) {// 右上for (int j = 1; j <= c; ++j) {dp[i][j][2] = max(dp[i][j - 1][2], dp[i + 1][j][2]) + a[i][j];}// 左上for (int j = c; j >= 1; --j) {dp[i][j][3] = max(dp[i + 1][j][3], dp[i][j + 1][3]) + a[i][j];}}int ans = 0;for (int i = 2; i < r; ++i) {for (int j = 2; j < c; ++j) {ans = max(ans, dp[i - 1][j][0] + dp[i + 1][j][3] + dp[i][j - 1][2] + dp[i][j + 1][1]);ans = max(ans, dp[i - 1][j][1] + dp[i + 1][j][2] + dp[i][j - 1][0] + dp[i][j + 1][3]);}}cout << ans << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF B. Working out的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。