Description
在一个H * W的网格中有若干个机器人和一个出口，其余是空地。每次你可以让所有机器人往某个方向移动一步。当机器人移动到出口时候会被取出，当机器人移出网格时会爆炸。求你最多取出多少机器人。
Solution
首先，考虑模型转换，注意到机器人移动等价于矩形+出口移动。那么我们记，\(dp[i][j][k][l]\)表示矩形\((i,j)-(k,l)\)中的机器人最多能有多少个被出口取出。
考虑转移，只说明向\(dp[i][j][k][l]\to dp[i][j][k][l]\)的转移，既向上转移一整行。然后可以被出口取出的一定是连续的一段机器人：
1、左端点：：\(，min(j-1,l-S_y)，j-1\)代表最左可以取到的机器人；\(l-S_y\)则表示最左边还没有移出网格的机器人
2、右端点：：\(，max(l,m-S_y+j)，l\)代表最右可以取到的机器人；\(m-S_y+j\)则表示最右边还没有移出网格的机器人
其余同理
最后答案就是\(ans=\sum_{1\leqslant i \leqslant S_x \leqslant k \leqslant n,1\leqslant j \leqslant S_y \leqslant l \leqslant m}{dp[i][j][k][l]}\)
！！！但是！！！
本题卡内存，所以short大法好
Hint
\(H,W \leqslant 100\)
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 101;
const int xx[4] = {-1,0,1,0};
const int yy[4] = {0,1,0,-1};
short dp[maxn][maxn][maxn][maxn], ans = -1;
short arr1[maxn][maxn], arr2[maxn][maxn];
int n, m, Sx, Sy;
char s[maxn][maxn];
inline short max1(short a, short b) { return (a < b) ? (b) : (a); }
inline short min1(short a, short b) { return (a > b) ? (b) : (a); }
int main() {
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++) {
scanf("%s", s[i] + 1);
for(int j = 1;j <= m;j ++) {
if(s[i][j] == 'E') Sx = i, Sy = j;
short now = (s[i][j] == 'o') ? (1) : (0);
arr1[i][j] = arr2[i][j] = now;
arr1[i][j] += arr1[i][j - 1];
arr2[i][j] += arr2[i - 1][j];
}
}
dp[Sx][Sy][Sx][Sy] = 0;
for(int i = Sx;i >= 1;i --) {
for(int j = Sy;j >= 1;j --) {
for(int k = Sx;k <= n;k ++) {
for(int l = Sy;l <= m;l ++) {
// int dx, dy;
short tmp;
// cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << dp[i][j][k][l] << endl;
//i
if(i > 1 && k - Sx < i - 1) {
short l1 = min1(l,m - Sy + j);
short l2 = max1(j - 1,l - Sy);
tmp = arr1[i - 1][l1] - arr1[i - 1][l2];
dp[i - 1][j][k][l] = max1(dp[i - 1][j][k][l],dp[i][j][k][l] + tmp);
}
// if(dx >= 1 && dy >= 1 && dx <= n && dy <= m && s[dx][dy] == 'o') {
// dp[i + 1][j][k][l] = max(dp[i + 1][j][k][l],dp[i][j][k][l] + 1);
// }
//j
if(j > 1 && l - Sy < j - 1) {
short l1 = min1(k,n - Sx + i);
short l2 = max1(i - 1,k - Sx);
tmp = arr2[l1][j - 1] - arr2[l2][j - 1];
dp[i][j - 1][k][l] = max1(dp[i][j - 1][k][l],dp[i][j][k][l] + tmp);
}
// if(dx >= 1 && dy >= 1 && dx <= n && dy <= m && s[dx][dy] == 'o') {
// dp[i][j + 1][k][l] = max(dp[i][j + 1][k][l],dp[i][j][k][l] + 1);
// }
//k
if(k < n && Sx - i < n - k) {
short l1 = min1(l,m - Sy + j);
short l2 = max1(j - 1,l - Sy);
tmp = arr1[k + 1][l1] - arr1[k + 1][l2];
dp[i][j][k + 1][l] = max1(dp[i][j][k + 1][l],dp[i][j][k][l] + tmp);
}
// if(dx >= 1 && dy >= 1 && dx <= n && dy <= m && s[dx][dy] == 'o') {
// dp[i][j][k + 1][l] = max(dp[i][j][k + 1][l],dp[i][j][k][l] + 1);
// }
//l
if(l < m && Sy - j < m - l) {
short l1 = min1(k,n - Sx + i);
short l2 = max1(i - 1,k - Sx);
tmp = arr2[l1][l + 1] - arr2[l2][l + 1];
dp[i][j][k][l + 1] = max1(dp[i][j][k][l + 1],dp[i][j][k][l] + tmp);
}
// if(dx >= 1 && dy >= 1 && dx <= n && dy <= m && s[dx][dy] == 'o') {
// dp[i][j][k][l + 1] = max(dp[i][j][k][l + 1],dp[i][j][k][l] + 1);
// }
}
}
}
}
for(int i = Sx;i >= 1;i --) {
for(int j = Sy;j >= 1;j --) {
for(int k = Sx;k <= n;k ++) {
for(int l = Sy;l <= m;l ++) ans = max1(ans,dp[i][j][k][l]);
}
}
}
cout << ans << endl;
return 0;
}
注释略多