AtCoder AGC004E Salvage Robots (DP)

题目链接

https://atcoder.jp/contests/agc004/tasks/agc004_e

题解

本题的难度不在于想到大体思路，而在于如何把代码写对。。

首先我们可以不让机器人动，让出口和边界一起动。

然后设\(dp[l][r][u][d]\)表示出口往四个方向分别动了最多\(l,r,u,d\)格，最大能圈住几个机器人。

转移以向下为例: 向下转移合法的条件为\(x_0+d<n-u\) (\(x_0,y_0\)为起点坐标)，因为出口的位置是\(x_0+d+1\), 而同时要满足点在网格上下边界圈成的合法矩形内，网格下边界的最上位置为\(n-u\).

注意向下合法和向上合法并不等价，比如一种情况是起点离上边界很近离下边界很远，就有可能出现先上后下能完成但是先下后上完不成的情况。

防止MLE可以滚动数组或者开short.

时间复杂度\(O(n^4)\).

代码

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cassert>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100;

short dp[N+3][N+3][N+3][N+3];

int s[N+3][N+3];

char a[N+3][N+3];

int n,m,sx,sy;

int getsum(int lx,int rx,int ly,int ry) {return s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1];}

int updmax(short &x,short y) {x = x>y?x:y;}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1; i<=n; i++) scanf("%s",a[i]+1);

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=m; j++)

		{

			s[i][j] = (a[i][j]=='o'?1:0)+s[i-1][j]+s[i][j-1]-s[i-1][j-1];

			if(a[i][j]=='E') {sx = i,sy = j;}

		}

	}

	memset(dp,213,sizeof(dp));

	dp[0][0][0][0] = 0; short ans = 0;

	for(int l=0; sy-l>0; l++)

	{

		for(int r=0; sy+r<=m; r++)

		{

			for(int u=0; sx-u>0; u++)

			{

				for(int d=0; sx+d<=n; d++)

				{

					updmax(ans,dp[l][r][u][d]);

					int ly = max(1+r,sy-l),ry = min(m-l,sy+r),lx = max(1+d,sx-u),rx = min(n-u,sx+d);

//					printf("l%d r%d u%d d%d x[%d,%d] y[%d,%d]\n",l,r,u,d,lx,rx,ly,ry);

					if(sx+d<n-u)

					{

						updmax(dp[l][r][u][d+1],dp[l][r][u][d]+getsum(sx+d+1,sx+d+1,ly,ry));

					}

					if(sx-u>1+d)

					{

						updmax(dp[l][r][u+1][d],dp[l][r][u][d]+getsum(sx-u-1,sx-u-1,ly,ry));

					}

					if(sy+r<m-l)

					{

						updmax(dp[l][r+1][u][d],dp[l][r][u][d]+getsum(lx,rx,sy+r+1,sy+r+1));

					}

					if(sy-l>1+r)

					{

						updmax(dp[l+1][r][u][d],dp[l][r][u][d]+getsum(lx,rx,sy-l-1,sy-l-1));

					}

				}

			}

		}

	}

	printf("%d\n",(int)ans);

	return 0;

}

巴特西

AtCoder AGC004E Salvage Robots (DP)

题目链接

题解

代码

最新文章

热门文章