BZOJ

BZOJ 3111

传送门

问题描述

在一个$n\times m$的棋盘上，每个格子有一个权值，初始时，在某个格子的顶点处一只面朝北的蚂蚁，我们只知道它的行走路线是如何转弯，却不知道每次转弯前走了多长。蚂蚁转弯是有一定特点的，即它的转弯序列一定是如下的形式：
右转，右转，左转，左转，右转，右转$cdots$左转，左转，右转，右转，右转。
即两次右转和两次左转交替出现的形式，最后两次右转（最后两次一定是右转）后再多加一次右转。我们还知道，蚂蚁不会在同一个位置连续旋转两次，并且蚂蚁行走的路径除了起点以外，不会到达同一个点多次，它最后一定是回到起点然后结束自己的行程，而且蚂蚁只会在棋盘格子的顶点处转弯。
设$k$为蚂蚁左转的次数除以$2$，当$k=0$时，蚂蚁可能行走的路径如下图
图挂了
转弯序列为：右转，右转，右转。
当$k=1$时，蚂蚁可能行走的路径如下图
图挂了
转弯序列为：右转，右转，左转，左转，右转，右转，右转。
现在已知棋盘大小、每个格子的权值以及左转次数$/2$的值，问蚂蚁走出的路径围出的封闭图形，权值之和最大可能是多少。

输入格式

在输入文件$ant.in$中，第一行三个数$n,m,k$。意义如题目描述。
接下来一个$n$行$m$列的整数矩阵，表示棋盘。

输出格式

在输入文件$ant.out$中，一个数，表示蚂蚁所走路径围出的图形可能的最大权值和。

样例输入

1
2
3
2 5 2
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

样例输出

1
-8

样例说明

除了第一行的第二个和第一行的第四个都要围起来才至少合法。

数据规模与约定

$10\%$的数据所有格子中权值均非负
另$20\%$的数据$n=2$
另$30\%$的数据$k=0$
$100\%$的数据$1\leq n\leq 100,1\leq m\leq 100,0\leq k\leq 10 $保证存在合法路径，数据有梯度，格子中每个元素的值绝对值不超过$10000$

把路径自己画一画就可以得出蚂蚁包围的图形其实就是底边在一条线上的一高一低$2\times k+1$个矩形，且第奇数个比两边高，第偶数个比两边低

先说明一下…以下的方程是按照矩形左下角为原点推的，但是因为代码里把矩形左上角存成原点比较方便…所以这些方程意会就好…

设$F_{i,j,k,l}$为当前是第$k$个矩形，矩形右下角为$(i,j)$，右上角为$(l,j)$时的最大权值和（之前的图形也要算进来），$sum[i,j]$为第$j$列中$1$到$i$的权值和

那么每次转移有两种情况，接着上一个矩形走或者新开一个矩形，所以

$$F_{i,j,k,l}=max(F_{i,j-1,k,l},F_{i,j-1,k-1,h})+sum[i,j]-sum[l-1,j](若k为奇数h\in[i,l),若k为偶数h\in(l,n])$$

后边那坨可以预处理出来

$$F1_{i,j,k,l}=max\lbrace F_{i,j,k,h},h\in[1,l)\rbrace$$
$$F2_{i,j,k,l}=max\lbrace F_{i,j,k,h},h\in(l,n]\rbrace$$

然后呢…$i$其实可以不用存在数组里，只用存后边3维就行了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
program bzoj_3111;
const inf=maxlongint>>1;
var f,f1,f2:array[0..100,0..21,1..100]of longint;
    sum:array[0..100,1..100]of longint;
    n,m,c,i,j,k,l,ans:longint;
 
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
 
begin
  readln(n,m,c);
  c:=c<<1+1;
  for i:=1 to m do sum[0,i]:=0;
  for i:=1 to n do
  for j:=1 to m do
  begin
    read(k);
    sum[i,j]:=sum[i-1,j]+k;
  end;
  for j:=1 to n do
  for k:=1 to c do
  begin
    f[0,k,j]:=-inf;
    f1[0,k,j]:=-inf;
    f2[0,k,j]:=-inf;
  end;
  ans:=-inf;
  for i:=1 to n do
  for j:=1 to m do
  begin
    for k:=1 to c do
    begin
      for l:=i downto 1 do if k and 1=1 then f[j,k,l]:=max(f[j-1,k,l],f1[j-1,k-1,l])+sum[i,j]-sum[l-1,j]
      else f[j,k,l]:=max(f[j-1,k,l],f2[j-1,k-1,l])+sum[i,j]-sum[l-1,j];
      f2[j,k,1]:=-inf;
      for l:=2 to i do f2[j,k,l]:=max(f2[j,k,l-1],f[j,k,l-1]);
      f1[j,k,i]:=-inf;
      for l:=i-1 downto 1 do f1[j,k,l]:=max(f1[j,k,l+1],f[j,k,l+1]);
    end;
    ans:=max(ans,max(f2[j,c,i],f[j,c,i]));
  end;
  writeln(ans);
end.