题目描述
给出一个H的行和W列的网格。第i行第j列的状态是由一个字母的A[i][j]表示，如下：
“.” 此格为空。
“o” 此格包含一个机器人。
“E” 此格包含一个出口，保证出口在整个网格中有且只有一个
每次可以选择上，下，左，右之一的方向，将所有剩余的机器人向这个方向移动一个格子，如果一个机器人被移出了网格，那么这个机器人会爆炸，并立即消失。如果一个机器人移动到出口所在的格子，机器人将获救，并消失，最多有多少机器人获救。
数据范围
对于100%的数据，n，m<=100
=w=
设
方程易推。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="aP3.in";
const char* fout="aP3.out";
const int inf=0x7fffffff;
const int maxn=107;
int n,m,i,j,k,l,ans,tot;
char a[maxn][maxn];
int sum[maxn][maxn];
int ex,ey;
int f[2][maxn][maxn][maxn],v;
int getsum(int sx,int sy,int tx,int ty){
if (sx>tx || sy>ty) return 0;
return sum[tx][ty]-sum[sx-1][ty]-sum[tx][sy-1]+sum[sx-1][sy-1];
}
int main(){
scanf("%d%d
",&n,&m);
for (i=1;i<=n;i++){
for (j=1;j<=m;j++){
a[i][j]=getchar();
if (a[i][j]=='o'){
sum[i][j]=1;
}else if (a[i][j]=='E'){
ex=i;
ey=j;
}
sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
scanf("
");
}
v=0;
for (i=0;i<=n;i++){
memset(f[1-v],0,sizeof(f[1-v]));
for (j=0;j<=m;j++)
for (k=0;k<=n;k++)
for (l=0;l<=m;l++){
if (ex+i>n || ex-k<1 || ey+j>m || ey-l<1) continue;
//if (ex<i || ex>n-k || ey<j || ey>m-l) continue;
if (ex+i+1<=n-k) f[1-v][j][k][l]=max(f[1-v][j][k][l],f[v][j][k][l]+getsum(ex+i+1,max(j+1,ey-l),ex+i+1,min(m-l,ey+j)));
if (ey+j+1<=m-l) f[v][j+1][k][l]=max(f[v][j+1][k][l],f[v][j][k][l]+getsum(max(i+1,ex-k),ey+(j+1),min(n-k,ex+i),ey+(j+1)));
if (ex-k-1>=1+i) f[v][j][k+1][l]=max(f[v][j][k+1][l],f[v][j][k][l]+getsum(ex-(k+1),max(j+1,ey-l),ex-(k+1),min(m-l,ey+j)));
if (ey-l-1>=1+j) f[v][j][k][l+1]=max(f[v][j][k][l+1],f[v][j][k][l]+getsum(max(i+1,ex-k),ey-(l+1),min(n-k,ex+i),ey-(l+1)));
ans=max(ans,f[v][j][k][l]);
}
v=1-v;
}
printf("%d",ans);
return 0;
}=o=
事实上，比赛中我已经注意到，如果强制某个机器人获救的话，必然牺牲的是连续的数行或数列。
利用这一点，就可以推出，对当前场面有影响的，就是上下左右四个方向牺牲的行列数。
由于
可惜我当时直往搜索的方向想，结果什么都没搞成。
这启示说，如果找到了代表某种场面，只需要很少参数的话，就可以利用动态规划了。