Atcoder题解：Agc004_e

第一步转化题意，我们把“所有机器人移动”转化成“出口带着边框移动”，而在出口运动过程中超出边框的机器人，就“死”了。

然后我们发现，出口运动过程中，假设出口目前走到的最左边的列是 \(l\)，以此类推定义 \(r,u,d\)，那么设一开始出口离四个方向边框的距离分别是 \(ml,mr,mu,md\)，那么对于 边框之外一定不会已经被遇到 的机器人而言，只要大于 \(l+mr-1\)，其贡献就已经变成 \(0\) 了，不会再产生贡献了。而我们目前在 \(l,r,u,d\) 限定的范围内运动，一定不会导致本来存活的机器人在移动后死亡。

那么，我们就可以设 \(dp\) 状态为 \(dp_{l,r,u,d}\) 表示当前出口走到的最左边的列是 \(l\)，类似定义 \(r,u,d\)，拯救的机器人个数最大值。

然后我们枚举当前往下是往上下左右哪个方向扩展。我们发现，如果我们往 \(l-1\) 列扩展，只要 \(u\) 和 \(d\) 的最值不改变，我们可以在这一列任意移动。所以我们就可以钦定当前机器人已经可以在 \(\{l,r,u,d\}\) 限定范围内移动且在这个范围内移动不会造成新贡献，并且往 \(l-1\) 转移就计算整个 \(l-1\) 列上 \([u,d]\) 的所有格子的贡献。

而 \(l-1\) 列上的有贡献的格子是一段区间 \([U,D]\)，\(U\) 首先要满足大于等于 \(u\)，其次要满足 \(d-mu+1\le U\)。\(D\) 同理。有且仅有子矩形 \(\{l-1,l-1,U,D\}\) 内的点会产生贡献，可以直接使用二维前缀和 \(O(1)\) 求出。

然后同理可得 \(r,u,d\) 的转移。这样的复杂度是 \(O(n^3)\)，乍一看常数不小，四次转移，每次做一次二维前缀和。但是实际上，我们只要剪掉所有贡献为 \(0\) 的转移，就可以了。因为我们相当于剪掉了所有处在某一端点向已经死绝的方向转移的所有转移，而这类转移在任何的图上都会出现在 \(\dfrac{3}{4}\) 的转移里。

int n,m,a[105][105],ansx,ansy;
int dp[105][105][105][105];
int ml,mr,mu,md;
int sum[105][105],tmp[105];
st s;
inline void upd(int &x,int y){
	x=max(x,y);
}
inline int query(int x,int y,int xx,int yy){
	if(x>xx||y>yy||x<1||y<1)return 0;
	return sum[xx][yy]-sum[xx][y-1]-sum[x-1][yy]+sum[x-1][y-1];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	rp(i,n){
		cin>>s;
		rp(j,m){
			if(s[j-1]=='o')a[i][j]=1;
			else if(s[j-1]=='E')ansx=i,ansy=j;
		}
	}
	ml=ansy,mr=m-ansy+1,mu=ansx,md=n-ansx+1;
	rp(i,n){
		rp(j,m){
			tmp[j]=tmp[j-1]+a[i][j];
			sum[i][j]=sum[i-1][j]+tmp[j];
		}
	}int ans=0;
	per(l,1,ansy)rep(r,ansy,m){
		per(u,1,ansx)rep(d,ansx,n){
			int res=dp[l][r][u][d];
			ans=max(ans,res);
			if(l-1>=r-ml+1){
				int U=max(u,d-mu+1),D=min(d,u+md-1);
				upd(dp[l-1][r][u][d],res+query(U,l-1,D,l-1));
			}
			if(r+1<=l+mr-1){
				int U=max(u,d-mu+1),D=min(d,u+md-1);
				upd(dp[l][r+1][u][d],res+query(U,r+1,D,r+1));
			}
			if(u-1>=d-mu+1){
				int L=max(l,r-ml+1),R=min(r,l+mr-1);
				upd(dp[l][r][u-1][d],res+query(u-1,L,u-1,R));
			}
			if(d+1<=u+md-1){
				int L=max(l,r-ml+1),R=min(r,l+mr-1);
				upd(dp[l][r][u][d+1],res+query(d+1,L,d+1,R));
			}
		}
	}cout<<ans<<endl;
	return 0;
}
//Crayan_r