[DP记录]AT2045 [AGC004E] Salvage Robots

**题意** ： 有一个 $n\times m$ 的棋盘，上面有若干机器人，以及恰好一个出口。 每次可以命令所有机器人向上下左右中的某个方向移动一格，如果它超出了棋盘的边界就会消失。如果它到了出口的位置就会被你救下(并且从棋盘上消失)。 求能够救下的机器人的最大值。 $n,m\leq 100$ ，时限$\texttt{2s}$ ，空限$\texttt{250M}$。 ------------ 根据运动的相对性，可以看做机器人不动，而出口和棋盘一起移动。 记出口向上、左、下、右移动的最大距离分别 $w,a,s,d$ 。记出口位置为 $(x_0,y_0)$。 出口可以到达的区域为 $[x_0-w,x_0+s][y_0-a,y+d]$。 而且，矩形 $[1+s,n-w][1+d,m-a]$ 外的机器人若没有被拯救，必然已消失。 于是可以设计 $\rm DP$。设 $dp[w][a][s][d]$ 为出口向上、左、下、右移动的最大距离分别 $w,a,s,d$，已经拯救的最多机器人个数。 当 $w,a,s,d$ 其中一个扩大时，计算出扩大的部分（一条）与未消失部分的交集，即可计算能多拯救的机器人数目。 时空复杂度均为 $O(n^4)$ 。为了卡空间，使用 `short` 存储 $\rm DP$ 数组。 具体转移细节见代码。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 105 using namespace std; 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; } char s[MaxN][MaxN]; int n,m; int main() { 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=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=max(ly2,ly);ry2=min(ry2,ry);} else {ly2=1;ry2=0;} dp[w+1][a][s][d]=max(dp[w+1][a][s][d],(short)(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=max(lx2,lx);rx2=min(rx2,rx);} else {lx2=1;rx2=0;} dp[w][a+1][s][d]=max(dp[w][a+1][s][d],(short)(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=max(ly2,ly);ry2=min(ry2,ry);} else {ly2=1;ry2=0;} dp[w][a][s+1][d]=max(dp[w][a][s+1][d],(short)(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=max(lx2,lx);rx2=min(rx2,rx);} else {lx2=1;rx2=0;} dp[w][a][s][d+1]=max(dp[w][a][s][d+1],(short)(dp[w][a][s][d]+qry2(y1,lx2,rx2))); } } printf("%d",(int)ans); return 0; } ```