题解：CF173C Spiral Maximum

· · 题解

思路

考虑暴力做法，枚举每个方形，时间复杂度显然 O(n^4)，CF 神机不 T 我吃。

于是优化，枚举起点边长一定优化不了，于是这只能优化求和。

仔细观察图片可以注意到，对于一个边长为 k 的方形，除去外面两圈的部分其他中心都与边长为 k-4 的方形相同，于是我们就可以由 k-4 递推而来，外面的一圈只需进行横向前缀和与竖向前缀和即可，最后改变绘画起点的那一格。由于 n^3 空间复杂度有点高（我这么认为），使用滚动优化一下。

code

我是压行大师

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,x,y) for(i=x;i<=y;i++)
#define rF(i,x,y) for(i=x;i>=y;i--)
int n,m,g[505][505],dp[5][505][505],s1[505][505],s2[505][505],i,j,k,ans=-2147483647; 
signed main()
{
    cin>>n>>m;
    F(i,1,n) F(j,1,m) cin>>g[i][j],s1[i][j]=s1[i][j-1]+g[i][j],s2[i][j]=s2[i-1][j]+g[i][j],dp[1][i][j]=g[i][j];
    for(k=3;k<=min(n,m);k+=2) F(i,1,n-k+1) F(j,1,m-k+1) dp[k%3][i][j]=dp[(k-1)%3][i+2][j+2]+s1[i][j+k-1]-s1[i][j-1]+s1[i+k-1][j+k-1]-s1[i+k-1][j-1]+s2[i+k-2][j]-s2[i][j]+s2[i+k-2][j+k-1]-s2[i][j+k-1]-g[i+1][j]+(k!=3)*g[i+2][j+1],ans=max(ans,dp[k%3][i][j]);//k由k-4转移而来，在mod3下差一
    cout<<ans;
    return 0;
}