动态规划

题意：

链接：https://ac.nowcoder.com/acm/problem/14294
来源：牛客网

给定一个n*m的矩阵，矩阵元素由X和O构成，请求出其中最大的由X构成的蝴蝶形状。
由X构成的蝴蝶形状的定义如下：
存在一个中心点，并且其往左上、左下、右上、右下四个方向扩展相同的长度（扩展的长度上都是X)，且左上顶点与左下顶点、右上顶点与右下顶点之间的格子全由X填充。我们不在意在蝴蝶形状内部是X还是O。
例如：
XOOOX
XXOXX
XOXOX
XXOXX
XOOOX
是一个X构成的蝴蝶形状。
X
也是。
而
XOOX
OXXO
OXXO
XOXX
不是（不存在中心点）。

输入描述:
第一行两个整数n, m表示矩阵的大小(1 <= n, m <= 2000)；
接下来n行，每行一个长度为m的字符串表示矩阵，矩阵元素保证由X和O构成。
输出描述:
一行一个整数表示最大的由X构成的蝴蝶形状的对角线的长度。
示例1
输入
复制
5 5
XOOOX
XXOXX
XOXOX
XXOXX
XOOOX
输出
复制
5

分析

这题是动态规划，我们可以很清楚的发现直接做是做不出来的。找不到转移状态。
那么我们可以分解这个问题
我们记
a[i][j]为(i,j)向右下延伸的最长距离
b[i][j]为(i,j)向下延伸的最长距离
c[i][j]为(i,j)向左下延伸的最长距离

另外我们还发现，他的外接矩形一定是一个奇数长的正方形！！

则，问题简单了：
我们可以利用动态规划轻易的计算出a,b,c
再对左上顶点进行枚举
根据a,b找到右上顶点，再进行判断是否可以构成蝴蝶

其实，我没有做出来。。。。。。看了人家的题解后恍然大悟！！

面向结果编程。。。。

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 2000 + 100;
char chs[max_n][max_n];
int a[max_n][max_n], b[max_n][max_n], c[max_n][max_n];
int ans = 0;

int main() {
    ios::sync_with_stdio(0);
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> chs[i][j];
    for (int i = n;i > 0;i--)
        for (int j = m;j > 0;j--)
            if (chs[i][j] == 'X') {
                a[i][j] = a[i + 1][j + 1] + 1;
                b[i][j] = b[i + 1][j] + 1;
                c[i][j] = c[i + 1][j - 1] + 1;
            }
    for (int i = 1;i <= n;i++) {
        if (n - i + 1 <= ans)break;
        for (int j = 1;j <= m;j++) {
            if (m - j + 1 <= ans)break;
            int k = min(a[i][j], b[i][j]);k--;
            if (k & 1)k--;
            while (k + 1) {
                if (k + 1 <= ans)break;
                int cmp = min(b[i][j + k], c[i][j + k]);
                if (cmp >= k) { ans = k + 1;break; }
                k -= 2;
            }
        }
    }cout << ans << endl;
}

这道题，动态规划的部分难点并不是在找转移方程，难点在于找状态。
我实在是没有想到，竟然可以使用多个动态规划方程数组，进行答案的组合！！！！
触及到思维盲区了，但其实仔细想想，这也是枚举的常规思路？