AGC004E Salvage Robots

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 有一个 的棋盘，上面有若干机器人，以及恰好一个出口。

每次可以命令所有机器人向上下左右中的某个方向移动一格，如果它超出了棋盘的边界就会消失。如果它到了出口的位置就会被你救下(并且从棋盘上消失)。

求能够救下的机器人的最大值。

，时限 ，空限 。

根据运动的相对性，可以看做机器人不动，而出口和棋盘一起移动。

记出口向上、左、下、右移动的最大距离分别 。记出口位置为 。

出口可以到达的区域为 。

而且，矩形 外的机器人若没有被拯救，必然已消失。

于是可以设计 。设 为出口向上、左、下、右移动的最大距离分别 ，已经拯救的最多机器人个数。

当 其中一个扩大时，计算出扩大的部分（一条）与未消失部分的交集，即可计算能多拯救的机器人数目。

时空复杂度均为 。为了卡空间，使用 short 存储 数组。

具体转移细节见代码。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <algorithm>
#include <cstdio>

const int MaxN = 105; 

short dp[MaxN][MaxN][MaxN][MaxN], o1[MaxN][MaxN], o2[MaxN][MaxN];
short qry1(int x,int l,int r) {
	return (l<=r) ? o1[x][r]-o1[x][l-1] : 0; 
}
short qry2(int y,int l,int r) {
	return (l<=r) ? o2[r][y]-o2[l-1][y] : 0;
}
void upd(short &u, short v) {
	u = std::max(u, v);
}
char s[MaxN][MaxN];

int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	int x0,y0;
	for (int i=1; i<=N; i++) {
		scanf("%s", s[i]+1);
		for (int j=1; j<=M; j++) {
			o1[i][j] = (s[i][j]=='o') + o1[i][j-1];
			o2[i][j] = (s[i][j]=='o') + o2[i-1][j];
			if (s[i][j]=='E')
				{x0=i; y0=j;}
		}
	}
	short ans = 0;
	for (int w=0; w<x0; w++)
		for (int a=0; a<y0; a++)
			for (int s=0; x0+s<=N; s++)
				for (int d=0; y0+d<=M; d++) {
					ans = std::max(ans, dp[w][a][s][d]);
					int lx=1+s, rx=N-w, ly=1+d, ry=M-a;
					if (w+1<x0) {
						int x1=x0-w-1, ly2=y0-a, ry2=y0+d;
						if (lx<=x1 && x1<=rx) {
							ly2 = std::max(ly2, ly);
							ry2 = std::min(ry2, ry);
						} else {ly2=1; ry2=0;}
						upd(dp[w+1][a][s][d], dp[w][a][s][d]+qry1(x1,ly2,ry2));
					}
					if (a+1<y0) {
						int y1=y0-a-1, lx2=x0-w, rx2=x0+s;
						if (ly<=y1 && y1<=ry) {
							lx2 = std::max(lx2, lx);
							rx2 = std::min(rx2, rx);
						} else {lx2=1; rx2=0;}
						upd(dp[w][a+1][s][d], dp[w][a][s][d]+qry2(y1,lx2,rx2));
					}
					if (x0+s<N) {
						int x1=x0+s+1, ly2=y0-a, ry2=y0+d;
						if (lx<=x1 && x1<=rx) {
							ly2 = std::max(ly2, ly);
							ry2 = std::min(ry2, ry);
						} else {ly2=1; ry2=0;}
						upd(dp[w][a][s+1][d], dp[w][a][s][d]+qry1(x1,ly2,ry2));
					}
					if (y0+d<M) {
						int y1=y0+d+1,lx2=x0-w,rx2=x0+s;
						if (ly<=y1 && y1<=ry) {
							lx2 = std::max(lx2, lx);
							rx2 = std::min(rx2, rx);
						} else {lx2=1; rx2=0;}
						upd(dp[w][a][s][d+1], dp[w][a][s][d]+qry2(y1,lx2,rx2));
					}
				}
	printf("%d", (int)ans);
	return 0;
}