【问题描述】
小空正在玩一个叫做捡金币的游戏。游戏在一个被划分成 n行 n列的网格状场地中进行。
每一个格子中都放着若干金币，并且金币的数量会随着时间而不断变化。 小空的任务就是在
网格中移动，拾取尽量多的金币。 并且，小空还有一个特殊技能“闪现”， 能帮助她在网格间
快速移动。
捡金币游戏的具体规则如下：在每一秒开始时，每个网格内都会出现一定数量的金币，
而之前在这格没有被拾取的金币就消失了。在游戏开始时，也就是第 1 秒的开始，小空可以
选择任意一个网格作为起点开始本次游戏，并拾取起点内的金币。之后，在下一秒到来前，
小空可以选择走路移动到与她所在的格子上、下、左、右相邻的一个格子中，或者呆在原地
不动，并在下一秒开始时拾取到她所在的格子中的金币。或者，小空可以选择使用闪现技能，
使用一次闪现时，她先选择上、下、左、右一个方向，之后向该方向移动两格。小空可以在
一秒内使用多次闪现，但不能超过 C 次。在一秒内使用的多次闪现必须向同一个方向移动，
若使用 x 次闪现，便可以向一个方向移动正好 2x 格，并且她也只能在下一秒开始时收集到
连续闪现结束后所在的那一格中的金币。如果在某一秒钟小空使用了闪现，那么她就不能选
择通过走路移动了，反过来也是如此。无论走路或者使用闪现，小空都不能移动到整个场地
之外。整个游戏共进行 T 秒，在第 T 秒开始时，小空将会拾取她所在的格子中的金币，并结
束游戏。 小空在整局游戏内一共只能使用最多 W 次闪现。
现在，给出游戏场地的大小 n，每秒钟开始时各个位置会出现的金币数，小空一秒内最
多使用闪现的次数 C， 小空在整局游戏中使用闪现的最多次数 W，整局游戏的总时间 T，请
你告诉小空她最多可以获得多少枚金币。
【输入】
输入的第 1 行包含 4 个整数 n， C， W， T，意义如问题描述中所述。
接下来包含 n 个 n*n 的矩阵，第 k 个矩阵的第 i 行第 j 列表示第 i 行第 j 列的格子在第 k
秒开始时出现的金币数（ 记作si,j,k）。 相邻两个矩阵间用一个空行隔开。
【 输出】
输出包含一个整数，表示游戏结束时小空最多可以获得的金币数量。
【输入输出样例 1】
| coin.in | coin.out |
| 3 1 1 3 1 3 4 3 2 1 1 3 2 2 3 1 1 3 2 2 1 4 3 3 1 3 2 1 2 3 1 |
11 |
见选手目录下的 coin / coin1.in 与 coin / coin1.out
【输入输出样例 1 说明】
选择在第 1 行第 3 列开始游戏， 获得 4 枚金币；在第 2 秒开始时向下闪现到第 3 行第 3
列， 获得 4 枚金币；在第 3 秒开始时向左走到第 3 行第 2 列，获得 3 枚金币， 游戏结束。一
共获得 11 枚金币。
【输入输出样例 2】
见选手目录下的 coin / coin2.in 与 coin / coin2.out
【数据规模与约定】
| 测试点编号 | n | C | W | T | si,j,k |
| 1 | ≤5 | ≤2 | ≤4 | ≤5 | ≤1,000 |
| 2 | |||||
| 3 | |||||
| 4 | ≤21 | ≤10 | ≤80 | ≤80 | |
| 5 | |||||
| 6 | |||||
| 7 | ≤25 | =100 | ≤150 | ≤100 | |
| 8 | |||||
| 9 | ≤12 | ||||
| 10 |
对 100%的数据， n≥1， C≥0， W≥0， T≥1， si,j,k≥0
/*
方程并不难，主要通过这个题学一下单调队列
*/
#include <cstdio>
#define inf 1000000007
int a[][][],f[][][][],q[],qc[],v[][],cnt,n,C,W,T,i,j,k,t,ii,jj,kk,tt,l,r,
ans,ch,tag; void read(int &x)
{
for (ch=getchar(); ch<=; ch=getchar());
for (x=; ch>; ch=getchar()) x = x*+ch-;
} void update(int &x, int y)
{
if (y > x) x = y;
} void clear()
{
l=; r=;
q[] = inf;
q[] = -inf;
cnt = ;
} void push(int x)
{
q[++r] = x;
qc[r] = ;
q[r+] = -inf;
while (q[r] >= q[r-])
{
qc[r-] += qc[r];
q[r-] = q[r];
q[r--] = -inf;
}
if (++cnt > C) if (--qc[l] == ) q[l++] = inf;
} int main()
{
freopen("coin.in", "r", stdin);
freopen("coin.out", "w", stdout);
scanf("%d%d%d%d", &n, &C, &W, &T);
for (t=; t<=T; ++t)
for (i=; i<=n; ++i)
for (j=; j<=n; ++j) read(a[t][i][j]);
for (i=; i<=n; ++i)
for (j=; j<=n; ++j) f[][i][j][] = a[][i][j];
t = ;
for (tt=; tt<=T; ++tt)
{
t ^= ;
for (i=; i<=n; ++i)
for (j=; j<=n; ++j)
for (k=; k<=W; ++k) f[t][i][j][k] = -inf;
for (i=; i<=n; ++i)
{
++tag;
for (jj=; jj<=n; ++jj)
for (kk=; kk<=W; ++kk)
if (v[jj][kk] != tag)
{
clear();
j = jj;
k = kk;
while (j<=n && k<=W)
{
v[j][k] = tag;
update(f[t][i][j][k], q[l]);
push(f[t^][i][j][k]);
j += ;
k++;
}
}
++tag;
for (jj=n; jj>=; --jj)
for (kk=; kk<=W; ++kk)
if (v[jj][kk] != tag)
{
clear();
j = jj;
k = kk;
while (j>= && k<=W)
{
v[j][k] = tag;
update(f[t][i][j][k], q[l]);
push(f[t^][i][j][k]);
j -= ;
k++;
}
}
}
for (j=; j<=n; ++j)
{
++tag;
for (ii=; ii<=n; ++ii)
for (kk=; kk<=W; ++kk)
if (v[ii][kk] != tag)
{
clear();
i = ii;
k = kk;
while (i<=n && k<=W)
{
v[i][k] = tag;
update(f[t][i][j][k], q[l]);
push(f[t^][i][j][k]);
i += ;
k++;
}
}
++tag;
for (ii=n; ii>=; --ii)
for (kk=; kk<=W; ++kk)
if (v[ii][kk] != tag)
{
clear();
i = ii;
k = kk;
while (i>= && k<=W)
{
v[i][k] = tag;
update(f[t][i][j][k], q[l]);
push(f[t^][i][j][k]);
i -= ;
k++;
}
}
}
for (i=; i<=n; ++i)
for (j=; j<=n; ++j)
for (k=; k<=W; ++k)
{
update(f[t][i][j][k], f[t^][i-][j][k]);
update(f[t][i][j][k], f[t^][i+][j][k]);
update(f[t][i][j][k], f[t^][i][j-][k]);
update(f[t][i][j][k], f[t^][i][j+][k]);
update(f[t][i][j][k], f[t^][i][j][k]);
f[t][i][j][k] += a[tt][i][j];
}
}
for (i=; i<=n; ++i)
for (j=; j<=n; ++j)
for (k=; k<=W; ++k) update(ans, f[t][i][j][k]);
printf("%d\n", ans);
return ;
}