Working Out

Posted on Edited on In Word count in article: 495 Reading time ≈ 2 mins.
Working Out

Working Out

##题目大意: 给定一个矩阵，每个点都有一个点权，让你求从矩阵中某一点到矩阵四个顶点的权值之和减去自己的四倍的值最大(就是这个点没有贡献)

分析：

我们画两张图，看看他们的路径，就会发现其实只有两种情况 一: 二：

就是说其实只有两种转移的方式

那么我们用4个数组分别记录到四个顶点的最大距离 然后再枚举每个点作为交点时的答案，不断更新 \[ ans=\max_{1<i<n,1<j<m}(dp[1][i - 1][j] + dp[3][i + 1][j] + dp[2][i][j + 1] + dp[4][i][j - 1],dp[1][i][j - 1] + dp[3][i][j + 1] + dp[2][i - 1][j] + dp[4][i + 1][j]) \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e3 + 10;

int dp[5][maxn][maxn];
int n, m, ans, a[maxn][maxn];

inline int max_(int a, int b)
{
    return a > b ? a : b;
}

inline int Read() 
{
	int x(0), f = 1;
    char ch = getchar();
	while (ch < '0' || ch > '9') { 
        if(ch == '-') f = -1;
        ch = getchar();
    }
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x * f;
}

int main()
{
    n = Read(), m = Read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) a[i][j] = Read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) 
            dp[1][i][j] = max_(dp[1][i - 1][j], dp[1][i][j - 1]) + a[i][j];

    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= 1; --j) 
            dp[2][i][j] = max_(dp[2][i - 1][j], dp[2][i][j + 1]) + a[i][j];

    for (int i = n; i >= 1; --i)
        for (int j = m; j >= 1; --j) 
            dp[3][i][j] = max_(dp[3][i + 1][j], dp[3][i][j + 1]) + a[i][j];

    for (int i = n; i >= 1; --i)
        for (int j = 1; j <= m; ++j) 
            dp[4][i][j] = max_(dp[4][i + 1][j], dp[4][i][j - 1]) + a[i][j];

    for (int i = 2; i < n; ++i)
        for (int j = 2; j < m; ++j)
            ans = max_ (ans, dp[1][i - 1][j] + dp[3][i + 1][j] + dp[2][i][j + 1] + dp[4][i][j - 1]), 
            ans = max_ (ans, dp[1][i][j - 1] + dp[3][i][j + 1] + dp[2][i - 1][j] + dp[4][i + 1][j]);
    
    printf ("%d\n", ans);
    system("pause");
}