自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 23:17:07，当前版本为作者最后更新于2025-06-12 23:55:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

有点复杂的 DP 题。

设 $UL(x,y)$ 表示从白格子 $(x,y)$ 开始向左上方连续白色格子数量，$UR(x,y)$ 表示从白格子 $(x,y)$ 开始向右上方连续白色格子数量，$V(x,y)=UL(x,y)+UR(x,y)-1$ 表示在白格子 $(x,y)$ 处执行 V 字形涂色时被涂色的格子数量。特别地，若 $(x,y)$ 为黑色，规定以上三个值均为 $0$。

可以根据 $x+y$ 的奇偶性将所有格子 $(x,y)$ 分为两类。注意到，一次 V 字形涂色中被涂色的所有格子均在同一类中。因此，若两次涂色选择的格子分别在两类中，它们之间必然不会互相干扰，两个 $V$ 值之和即为被涂色的格子数量$^{[1]}$。

下面讨论两次涂色选择的格子在同一类中的情况。

若一个 V 形被包含在另一个 V 形的直角内，它们之间也不会互相影响。设 $B(x,y)$ 表示顶点在 $(x,y)$ 及其 V 形的直角内的所有 V 形的最大 $V$ 值，不难得到其转移：

$$B(x,y)=\max\{B(x-1,y-1),B(x-1,y),B(x-1,y+1),V(x,y)\} $$

所有 $V(x,y)+B(x-1,y)$ 可以用于更新答案$^{[2]}$。

否则，或者先对左侧进行涂色，得到完整的左侧 V 形以及受左侧影响的不完整的右侧 V 形，或者先对右侧进行涂色，得到完整的右侧 V 形以及受右侧影响的不完整的左侧 V 形。注意到，第一种情况中的两个部分可以被一条 $x+y=k$ 的直线分隔开，第二种情况中的两个部分可以被一条 $x-y=k$ 的直线分隔开。

设 $LV(x,y)$ 表示从白格子 $(x,y)$ 出发，先向左下方走若干个白色格子（也可以不走），再向左上方走若干个白色格子，最多有多少个格子；$RV(x,y)$ 表示从白格子 $(x,y)$ 出发，先向右下方走若干个白色格子（也可以不走），再向右上方走若干个白色格子，最多有多少个格子。不难得到其转移：

$$\begin{aligned} LV(x,y)&=\max\{UL(x,y),LV(x+1,y-1)+1\}\\ RV(x,y)&=\max\{UR(x,y),RV(x+1,y+1)+1\}\\ \end{aligned} $$

分别统计 $x+y\le k$ 时 $V$ 的最大值、$x+y\ge k$ 时 $RV$ 的最大值，即可求出第一种情况的答案$^{[3]}$；分别统计 $x-y\le k$ 时 $LV$ 的最大值、$x-y\ge k$ 时 $V$ 的最大值，即可求出第二种情况的答案$^{[4]}$。

取 $[1][2][3][4]$ 四种情况答案的最大值即为最终答案。

时间复杂度 $O(nm)$。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 3e3 + 5;

int n, m, a[N][N], UL[N][N], UR[N][N], V[N][N], LV[N][N], RV[N][N], pLV[N << 1], pRV[N << 1], fLV[N << 1], fRV[N << 1], B[N][N];
string s[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n) cin >> s[i];
    rep(i, 1, n) rep(j, 1, m) a[i][j] = s[i][j - 1] - '0';
    rep(i, 1, n) {
        rep(j, 1, m) {
            if(a[i][j]) {
                UL[i][j] = UL[i - 1][j - 1] + 1;
                UR[i][j] = UR[i - 1][j + 1] + 1;
                V[i][j] = UL[i][j] + UR[i][j] - 1;
            }
            B[i][j] = max({B[i - 1][j - 1], B[i - 1][j], B[i - 1][j + 1], V[i][j]});
        }
    }
    per(i, n, 1) {
        rep(j, 1, m) {
            if(a[i][j]) {
                LV[i][j] = max(UL[i][j], LV[i + 1][j - 1] + 1);
                RV[i][j] = max(UR[i][j], RV[i + 1][j + 1] + 1);
                chkmax(pLV[j + n - i + 1], LV[i][j]);
                chkmax(pRV[i + j], RV[i][j]);
                chkmax(fLV[j + n - i + 1], V[i][j]);
                chkmax(fRV[i + j], V[i][j]);
            }
        }
    }
    rep(i, 1, n + m) {
        chkmax(pLV[i], pLV[i - 1]);
        chkmax(fRV[i], fRV[i - 1]);
    }
    per(i, n + m, 1) {
        chkmax(pRV[i], pRV[i + 1]);
        chkmax(fLV[i], fLV[i + 1]);
    }
    int oM = 0, eM = 0;
    rep(i, 1, n) {
        rep(j, 1, m) {
            if((i + j) & 1) chkmax(oM, V[i][j]);
            else chkmax(eM, V[i][j]);
        }
    }
    int ans = oM + eM;
    rep(i, 1, n + m - 1) {
        chkmax(ans, pLV[i] + fLV[i + 1]);
        chkmax(ans, fRV[i] + pRV[i + 1]);
    }
    rep(i, 1, n) {
        rep(j, 1, m) {
            chkmax(ans, V[i][j] + B[i - 1][j]);
        }
    }
    cout << ans << endl;
    return 0;
}