递推一个数组f(i,j)，表示取了一个以(i,j)为右下角的矩形以后，在其右边和下面还能取到的最大矩形的面积，至于为什么只需要在右下范围内取就自己思考一下吧。
不过因为没有一组数据是输出“impossible”的，所以我就偷了个懒没有判断什么时候取不出两个矩形，这个就看最下面的题解吧
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 1000000000;
const int maxn = 1000 + 10;

int n, m, a, b;
int prefix_sum[maxn][maxn];
int num[maxn][maxn];
int f[maxn][maxn];

int sum (int x1, int y1, int x2, int y2) {
return prefix_sum[x2][y2] - prefix_sum[x2][y1-1] - prefix_sum[x1-1][y2] + prefix_sum[x1-1][y1-1];
}

int main ()
{
cin >> n >> m >> a >> b;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &num[i][j]);
prefix_sum[i][j] = num[i][j] + prefix_sum[i][j-1] + prefix_sum[i-1][j] - prefix_sum[i-1][j-1];
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = -INF;

for (int i = n-1; i >= 1; i--) { //递推边界
if (i < n-1) f[i][m] = f[i+1][m];
if (i+a <= n) for (int j = 1; j+b-1 <= m; j++)
f[i][m] = max(f[i][m], sum(i+1, j, i+a, j+b-1));
if (i+b <= n) for (int j = 1; j+a-1 <= m; j++)
f[i][m] = max(f[i][m], sum(i+1, j, i+b, j+a-1));
}

for (int j = m-1; j >= 1; j--) { //递推边界
if (j < m-1) f[n][j] = f[n][j+1];
if (j+a <= m) for (int i = 1; i+b-1 <= n; i++)
f[n][j] = max(f[n][j], sum(i, j+1, i+b-1, j+a));
if (j+b <= m) for (int i = 1; i+a-1 <= n; i++)
f[n][j] = max(f[n][j], sum(i, j+1, i+a-1, j+b));
}

for (int i = n-1; i >= 1; i--)
for (int j = m-1; j >=1; j--)
f[i][j] = max(f[i+1][j], f[i][j+1]);

int ans = -INF;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (i >= a && j >= b)
ans = max(ans, sum(i-a+1, j-b+1, i, j)+f[i][j]);
if (j >= a && i >= b)
ans = max(ans, sum(i-b+1, j-a+1, i, j)+f[i][j]);
}

cout << ans << "\n";
return 0;
}
```

├ 测试数据 01：答案正确... (47ms, 20044KB) 

├ 测试数据 02：答案正确... (0ms, 20044KB) 

├ 测试数据 03：答案正确... (16ms, 20040KB) 

├ 测试数据 04：答案正确... (297ms, 20044KB) 

├ 测试数据 05：答案正确... (297ms, 20044KB) 

├ 测试数据 06：答案正确... (390ms, 20044KB) 

├ 测试数据 07：答案正确... (63ms, 20040KB) 

├ 测试数据 08：答案正确... (390ms, 20044KB) 

├ 测试数据 09：答案正确... (406ms, 20044KB) 

├ 测试数据 10：答案正确... (437ms, 20044KB) 

var

  n,m,a,b,i,j,ans:longint;

  ff,sum,w:array[0..1001,0..1001]of longint;

  f:array[0..1000,0..1000,1..2]of longint;

procedure deal(a,b,u:longint);

var i,j:longint;

begin

  for i:=1 to n do

  for j:=1 to m do sum:=sum+ff;

  for i:=1 to n do

  for j:=1 to m+1-b do f:=sum-sum;

  for i:=1 to n do

  for j:=1 to m+1-b do sum:=sum+f;

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

  for j:=1 to m+1-b do f:=sum-sum;

end;

function max(x,y:longint):longint;

begin

  if x>y then max:=x else max:=y;

end;

procedure dp;

var i,j:longint;

begin

  for i:=1 to n+1 do

  for j:=1 to m+1 do w:=-1000000000;

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

  for j:=1 to m+1-b do

  begin

    if f>w then w:=f;

    if f>w[1,j] then w[1,j]:=f;

  end;

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

  for j:=1 to m+1-a do

  begin

    if f>w then w:=f;

    if f>w[1,j] then w[1,j]:=f;

  end;

  for i:=n downto 2 do

  if w>w then w:=w;

  for j:=m downto 2 do

  if w[1,j]>w[1,j-1] then w[1,j-1]:=w[1,j];

  ans:=-1000000000;

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

  for j:=1 to m+1-b do

  if f+max(w,w[1,j+b])>ans then ans:=f+max(w,w[1,j+b]);

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

  for j:=1 to m+1-a do

  if f+max(w,w[1,j+a])>ans then ans:=f+max(w,w[1,j+a]);

end;

begin

  read(n,m,a,b);

  for i:=1 to n do

  for j:=1 to m do read(ff);

  deal(a,b,1);

  deal(b,a,2);

  dp;

  if ans-1000000000 then writeln(ans) else writeln('Impossible');

end.

这题考的不是DP，是淡定。手一抖你就没了。

type

arr=array[0..1001,0..1001] of int64;

const

min:int64=-1 shl 62;

var

ans:int64;

n,m,i,j,a,b:longint;

sum,f,g,v:arr;

procedure init(var a:arr);

var

i:longint;

begin

for i:=0 to n+1 do

begin

a:=min;

a:=min;

end;

for i:=0 to m+1 do

begin

a[0,i]:=min;

a[n+1,i]:=min;

end;

end;

function max(a,b,c,d:int64):int64;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

if d>max then max:=d;

end;

function calc(x1,y1,x2,y2:longint):int64;

begin

if (x1m) then calc:=min

else calc:=sum[x2,y2]-sum[x1-1,y2]-sum[x2,y1-1]+sum[x1-1,y1-1];

end;

function calc0(x1,y1,x2,y2:longint):int64;

begin

if (x1m) then calc0:=min

else if max(f[x1-1,m],f[n,y1-1],g[1,y2+1],g[x2+1,1])=min then calc0:=min

else calc0:=calc(x1,y1,x2,y2)+max(f[x1-1,m],f[n,y1-1],g[1,y2+1],g[x2+1,1]);

end;

begin

readln(n,m,a,b);

for i:=1 to n do

begin

for j:=1 to m do

read(v);

readln;

end;

for i:=1 to n do

for j:=1 to m do

sum:=sum+sum-sum+v;

init(f);

init(g);

for i:=1 to n do

for j:=1 to m do

f:=max(f,f,calc(i-a+1,j-b+1,i,j),calc(i-b+1,j-a+1,i,j));

for i:=n downto 1 do

for j:=m downto 1 do

g:=max(g,g,calc(i,j,i+a-1,j+b-1),calc(i,j,i+b-1,j+a-1));

ans:=min;

for i:=1 to n do

for j:=1 to m do

ans:=max(min,ans,calc0(i-a+1,j-b+1,i,j),calc0(i-b+1,j-a+1,i,j));

if ans=min then writeln('Impossible')

else writeln(ans);

end.

无人题解。。菜鸟来献丑。。

首先 判断impossible的情况：

1 ((2*x

不会写，提供一个解题博客，但是还是不太懂，希望有好的题解。博客链接