趣题！
前缀和+dp+枚举分割线 == AC
```c++
#include <bits/stdc++.h>
using namespace std;

long long m[1005][1005], sum[1005][1005], dp[1005][1005], dp2[1005][1005];
long long n, k;

inline long long mark1(int i, int j)
{
if (i < k || j < k || j > n || i > n) return LONG_MIN;
return sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k];
}

inline long long mark2(int i, int j)
{
return mark1(i+k-1, j+k-1);
}

int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &m[i][j]);
for (int i = 0; i <= n; i++)
sum[0][i] = sum[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
sum[i][j] = m[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
for (int i = 0; i <= n+2; i++)
for (int j = 0; j <= n+2; j++)
dp[i][j] = dp2[i][j] = LONG_MIN;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = max(mark1(i, j), max(dp[i-1][j], dp[i][j-1]));
for (int i = n; i >= 1; i--)
for (int j = n; j >= 1; j--)
dp2[i][j] = max(mark2(i, j), max(dp2[i+1][j], dp2[i][j+1]));
long long ans = LONG_MIN;
for (int i = 1; i < n; i++) {
ans = max(ans, dp[n][i]+dp2[1][i+1]);
ans = max(ans, dp[i][n]+dp2[i+1][1]);
}
cout << ans << endl;
return 0;
}

玄学
#include <cstdio>
#include <algorithm>
#define Q 1010
using std::max;
using std::min;

int A[Q][Q],n,k;
int p[Q][Q]={0},p1[Q][Q]={0},p2[Q][Q]={0};
int f1[Q]={0},f2[Q]={0};

int main(){
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&A[i][j]);
//预处理:
//横向
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
p1[i][1]+=A[i][j];
for(int i=1;i<=n;i++)
for(int j=2;j<=n-k+1;j++)
p1[i][j]=p1[i][j-1]-A[i][j-1]+A[i][j+k-1];
//纵向
for(int j=1;j<=n;j++)
for(int i=1;i<=k;i++)
p2[1][j]+=A[i][j];
for(int j=1;j<=n;j++)
for(int i=2;i<=n-k+1;i++)
p2[i][j]=p2[i-1][j]-A[i-1][j]+A[i+k-1][j];
//p[][]
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
p[1][1]+=A[i][j];
for(int i=2;i<=n-k+1;i++)
p[i][1]=p[i-1][1]-p1[i-1][1]+p1[i+k-1][1];
for(int i=1;i<=n-k+1;i++)
for(int j=2;j<=n-k+1;j++)
p[i][j]=p[i][j-1]-p2[i][j-1]+p2[i][j+k-1];
//f1 f2
for(int i=n-k+1;i>=1;i--)
for(int j=n-k+1;j>=1;j--){
f1[i]=max(f1[i],max(f1[i+1],p[i][j]));
f2[j]=max(f2[j],max(f2[j+1],p[i][j]));
}
//枚举
int ans=0,m=0;
for(int i=1;i<=n-k+1;i++)
for(int j=1;j<=n-k+1;j++){
m=p[i][j]+max(f1[i+k],f2[j+k]);
ans=max(ans,m);
}
printf("%d",ans);

return 0;
}

你好

你可以枚举分割线

无限膜拜181818181818神牛无敌题解..........

枚举分割线O(n^2)

注意常数优化就可以秒杀

同样是puppy,用c读入341ms,用c++读入2100ms+4点TLE,差这么多！！！

好想的DP，但编起来很乱

begin

readln(n,k);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(a);

f:=f+f-f+a;

end;

end;

for i:=1 to n-k+1 do

for j:=1 to n-k+1 do

g:=f-f-f+f;

for i:=1 to n-k+1 do

begin

l:=l;

for j:=1 to n-k+1 do

if g>l then l:=g;

end;

for i:=n-k+1 downto 1 do

begin

r[i]:=r;

for j:=1 to n-k+1 do

if g>r[i] then r[i]:=g;

end;

for i:=1 to n-k+1 do

begin

u:=u;

for j:=1 to n-k+1 do

if g[j,i]>u then u:=g[j,i];

end;

for i:=n-k+1 downto 1 do

begin

d[i]:=d;

for j:=1 to n-k+1 do

if g[j,i]>d[i] then d[i]:=g[j,i];

end;

ans:=0;

for i:=1 to n-k do

if l[i]+r>ans then ans:=l[i]+r;

for i:=1 to n-k do

if u[i]+d>ans then ans:=u[i]+d;

writeln(ans);

end.

总算AC了。总算AC了。。。

最后我要说：细节！

最后我还要说：So Easy!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

总算过了

轻轻的 我看错了题目

狠狠地 我超时了25秒

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：20 有效耗时：0ms

动态规划O(n^2)必过

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 41ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：138ms

AC的不容易啊~~~~

细节~！！！！

此题的最初思路就是枚举第一个方阵~~~~然后 在剩余的区域找第二个方阵，求出两个方阵和的最大值。

其实最后的做法也是这个 只是加了点优化~~~~优化到了O(n^2)

先 求 sum[i][j] 就是以 (i,j)为左上角 边长为K的方阵。

求之前先求一个 p[i][j] q[i][j] 就是以(i,j)为开头 横向连续k个数的和 和 竖向 的和。

然后 sum[i][j]进行递推：

if(j == 0) sum[i][j] = sum[j] - q[j] + q[i + k - 1][j];

else sum[i][j] = sum[i][j-1] - p[i][j-1] + p[i][j + k - 1];

接下来在求一个h[i] g[i] 分别表示 横坐标从 i到最右端 及 纵坐标 从 i 到最右端 的 一个边长为k的方阵的最大和。

最后求按照最初思路来 枚举求就可以了：

for(int i = 0;i < n;++i)

{

if(i+k>n) break;

for(int j = 0;j < n;++j)

{

if(j+k>n) break;

ans = max(ans,max(g[j+k],h)+sum[i][j]);

}

}

注意：如果当预处理时边长不够k那么我赋值-maxlongint

终于AC！

我是先把所有K*K的值排序（快排）。

然后N次枚举分割线。

然后从N downto

找到合适的两个可以的值就退出，和答案比较，再枚举下条分割线。

就这样不是很完美的AC了。。嘿。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 88ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：444ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

为了等puppy，为了一道已经AC的题降了好几个点= =

之前打错了一组坐标，错了好几次。

dp

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 72ms

├ 测试数据 06：答案正确... 118ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 87ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：277ms

终于纠结过了

类似APIO2009第一题..可以找到一条线使得两个正方形分属两边，然后DP

枚举+剪枝=AC

我的方法应该有所不同吧：我枚举各个点作每个矩形的左上角，再枚举各个不相交的矩形的和最大