CF173C Spiral Maximum 题解

题意

求一个 \(n \times m\) 的矩形中螺旋形最大的数字和。

分析

看图不难发现，以同一个方块为中心的两个边长差为 \(2\) 的螺旋形的数字和其实是有规律的，大一些的螺旋形的数字和就等于整个正方形的数字和减去小一些的螺旋形数字和再减去小螺旋形左上角左侧的数。因此我们先用二维前缀和预处理每一个正方形的面积，然后循环每一个中心，递推出以 \((i,j)\) 为中心，从 \((i,j)\) 向边缘有 \(k\) 个方格的螺旋形的数字和。

dp[i][j][k]=sum(i,j,k)-dp[i][j][k-1]-a[i-k+1][j-k],ans=qmax(ans,dp[i][j][k]); 

代码

#include 
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int MAXN=503;
const int inf=2139062143;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
	register T1 x=0;register bool f=false;char ch=getchar();
	while(ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch>='0') x=(x*10)+(ch^48),ch=getchar();
	x=(f?-x:x);a=x;qread(b...);
}
templateinline T1 qmax(const T1 &x,const T2 &y){return x>y?x:y;}
templateinline T1 qmin(const T1 &x,const T2 &y){return x