P3086图八Figure Eight/JZOJ3235数字八

Iota2029 · 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;
}