【agc004e】Salvage Robots

题目大意

一个n*m的矩阵，矩阵内有一个出口和若干个机器人，每一步操作可以使所有的机器人向任意方向移动一格，如果机器人出了边界就爆炸。求最多可以让多少个机器人走到出口。

解题思路

发现，移动所有机器人，其实就相当于移动出口和边界。

于是，设f[i][j][k][l]，表示机器人走完了子矩阵(i,j)(k,l)，最多可以让多少个机器人走到出口。

每次多加一行或一列转移，根据边界来看增加的机器人数。

详细看程序。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <bitset>

#include <set>

const int maxlongint=2147483647;

const int mo=1e9+7;

const int N=105;

using namespace std;

short f[N][N][N][N],n,m,a[N][N],ans,sx,sy,v[N][N],v1[N][N];

int main()

{

	cin>>n>>m;

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

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

		{

			char c=getchar();

			while(c!='.' && c!='o' && c!='E') c=getchar();

			v[i][j]=v1[i][j]=a[i][j]=(c=='o');

			v[i][j]+=v[i][j-1];

			v1[i][j]+=v1[i-1][j];

			if(c=='E') sx=i,sy=j;

		}

	for(short i=sx;i>=1;i--)

		for(short j=sy;j>=1;j--)

			for(short i1=sx;i1<=n;i1++)

				for(short j1=sy;j1<=m;j1++)

				{

					if(1<i && i1+1<sx+i)

						f[i-1][j][i1][j1]=max((int)f[i-1][j][i1][j1],(int)f[i][j][i1][j1]+v[i-1][min((int)j1,m-sy+j)]-v[i-1][max((int)j-1,j1-sy)]);

        			if(i1<n && sx+i1<n+i)

        				f[i][j][i1+1][j1]=max((int)f[i][j][i1+1][j1],(int)f[i][j][i1][j1]+v[i1+1][min((int)j1,m-sy+j)]-v[i1+1][max((int)j-1,j1-sy)]);

        			if(1<j && j1+1<sy+j)

        				f[i][j-1][i1][j1]=max((int)f[i][j-1][i1][j1],(int)f[i][j][i1][j1]+v1[min((int)i1,n-sx+i)][j-1]-v1[max((int)i-1,i1-sx)][j-1]);

        			if(j1<m && sy+j1<m+j)

        				f[i][j][i1][j1+1]=max((int)f[i][j][i1][j1+1],(int)f[i][j][i1][j1]+v1[min((int)i1,n-sx+i)][j1+1]-v1[max((int)i-1,i1-sx)][j1+1]);

				}

for(short i=sx;i>=1;i--)

		for(short j=sy;j>=1;j--)

			for(short i1=sx;i1<=n;i1++)

				for(short j1=sy;j1<=m;j1++) ans=max(f[i][j][i1][j1],ans);

	cout<<ans<<endl;

}

巴特西

【agc004e】Salvage Robots

题目大意

解题思路

最新文章

热门文章