清北学堂模拟day4 捡金币

【问题描述】
小空正在玩一个叫做捡金币的游戏。游戏在一个被划分成 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 ;
}
上一篇:深入JavaScript对象(Object)与类(class),详细了解类、原型


下一篇:jmeter生成报告指示板