自动搬运

查看原文

来自洛谷，原作者为

	Iota2029 **

搬运于2025-08-24 21:45:10，当前版本为作者最后更新于2019-07-12 07:16:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题其实是一道DP。

首先设$f[k][i][j]$表示到第$k$行上面矩阵的面积。
设$g[k][i][j]$表示从第$k$行往下的下面矩阵的面积。

然后转移很显然。。。指针$O(n^3)$的时间扫一扫求面积就好了。

然后可以发现，方便转移，$f[k][i][j]$可以赋值他所包含的$f[k'][i'][j']$。

最后，我们发现空间炸了！！！（hasikid！！！）

于是，题解在这里产生了分支：

1.把类型转成$short$。然后这样的话就可以拿九十分。

2.考虑到$g$可以不记录，及时枚举和$f$一起求，所以可以把$g$压掉，等到求最终答案的时候再一起求。

上码：

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#define N 301
using namespace std;

inline int max(int a,int b) {return a > b ? a : b;} 
int f[N][N][N];
int sum[N][N], map[N][N], n, ans, p;
char s[N];

int main()
{
   scanf("%d", &n);
   for (int i = 1;i <= n; ++i)
   {
   	scanf("%s", s + 1);
   	for (int j = 1;j <= n; ++j)
   		map[i][j] = s[j] == '*' ? 1 : 0, 
   		sum[i][j] = sum[i][j - 1] + map[i][j];
   }
   for (int i = 1;i < n - 1; ++i)
   	for (int j = i + 2;j <= n; ++j)
   	{
   		p = 0;
   		for (int k = 1;k <= n; ++k)
   		{
   			if (map[k][i] || map[k][j]) p = 0;
   			if (sum[k][i - 1] == sum[k][j]) 
   				!p ? p = k : f[k][i][j] = (k - p - 1) * (j - i - 1);
   		}
   	}
   for (int k = 1;k <= n; ++k)
   {
   	for (int j = n;j > 3; --j)
   		for (int i = j - 3;i >= 0; --i) 
   			if (sum[k][i - 1] == sum[k][j]) f[k][i][j] = max(f[k][i][j], f[k][i + 1][j]);
   	for (int i = 1;i < n - 1; ++i)
   		for (int j = i + 3;j <= n; ++j) 
   			if (sum[k][i - 1] == sum[k][j]) f[k][i][j] = max(f[k][i][j], f[k][i][j - 1]);
   }
   for (int i = 1;i < n - 1; ++i)
   	for (int j = i + 2;j <= n; ++j) 
   	{
   		p = 0;
   		for (int k = n;k; --k) 
   		{
   			if (map[k][i] || map[k][j]) p = 0;
   			if (sum[k][i - 1] == sum[k][j]) (!p) ? p = k : ans = max(ans, f[k][i][j] * (p - k - 1) * (j - i - 1));
   		}
   	}
   if (!ans) printf("-1");
   else printf("%d", ans);
   return 0;
}