这题怎么说,就是有点费脑子(确信)

一想n最大取400,随便模拟肯定是O( n ^ 4 ) 会超时，所以我们需要一种更好的方法来优化

首先引出我用到的几何真命题

如果平面直角坐标系上一个正方形一条对角线上点坐标已知,那么另外两点的坐标一定可以通过这两个点推出来

接下来看这道题,题面主对角线的意思就是正方形左上角到右下角的对角线,累计和差嘛,所以前缀和是我们可以想到的

所以做法就是定义f数组为以这个点为右下角的美丽值之和
同时定义g数组为以这个点为左下角的美丽值之和
这样就可以通过前缀和解决这个问题了

OIWiki对前缀和的解释

这是f,g数组初始化代码

for( int i = 1 ; i <= n ; i ++ )
{
    for( int j = 1 ; j <= n ; j ++ )
    {
        f[ i ][ j ] = f[ i - 1 ][ j - 1 ] + a[ i ][ j ] ;
        g[ i ][ j ] = g[ i - 1 ][ j + 1 ] + a[ i ][ j ] ;
    }
}

因为我们是从1开始的,我们事先定义数组时f,g[ 0 ][ x ] 和 f,g[ x ][ 0 ] 一定都为0,并且在开数组时我们可以把f,g数组的大小开到n最大值+1,这样就不用担心越界问题

由上面的真命题就可以得到我们只需要模拟其中一条对角线,另一条对角线的坐标就可以通过这个对角线两个点的坐标来推理出来,这是代码

原理就是模拟每一条主对角线并通过前缀和计算美丽值之差更新答案

for( int i = 1 ; i <= n - 1 ; i ++ ) // n-1因为一个对角线的左上角一定不在最后一行和最后一列
{
    for( int j = 1 ; j <= n - 1 ; j ++ )
    {
        int t1 = i + 1 , t2 = j + 1 ;
        while( t1 <= n and t2 <= n )
        {
            int t3 = f[ t1 ][ t2 ] - f[ i - 1 ][ j - 1 ] ;
            int t4 = g[ t1 ][ j ] - g[ i - 1 ][ t2 + 1 ] ;
            ans = max( ans , t3 - t4 ) ;
            t1 ++ , t2 ++ ;
        }
    }
}

最后输出即可

完整代码

#include<bits/stdc++.h>
using namespace std;
int n , a[ 401 ][ 401 ] ;
int f[ 401 ][ 401 ] , g[ 401 ][ 401 ] ;
int ans = INT_MIN ;
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 1 ; j <= n ; j ++ )
        {
            cin >> a[ i ][ j ] ;
        }
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 1 ; j <= n ; j ++ )
        {
            f[ i ][ j ] = f[ i - 1 ][ j - 1 ] + a[ i ][ j ] ;
            g[ i ][ j ] = g[ i - 1 ][ j + 1 ] + a[ i ][ j ] ;
        }
    }
    for( int i = 1 ; i <= n - 1 ; i ++ )
    {
        for( int j = 1 ; j <= n - 1 ; j ++ )
        {
            int t1 = i + 1 , t2 = j + 1 ;
            while( t1 <= n and t2 <= n )
            {
                int t3 = f[ t1 ][ t2 ] - f[ i - 1 ][ j - 1 ] ;
                int t4 = g[ t1 ][ j ] - g[ i - 1 ][ t2 + 1 ] ;
                ans = max( ans , t3 - t4 ) ;
                t1 ++ , t2 ++ ;
            }
        }
    }
    cout << ans ;
    return 0;
}