P12650 [KOI 2024 Round 2] 双 v 字形涂色

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定一个 $N$ 行 $M$ 列的网格图，每个格子被涂成白色或黑色。 定义以下操作为一次“V 字形涂色”： 1. 选择一个白色格子作为起点； 2. 从该格子开始，沿左上对角线（即每次向左上方移动一格）前进，直到遇到非白色格子或越出网格为止，将经过的所有格子涂为蓝色； 3. 从起点的右上方一格开始，沿右上对角线（即每次向右上方移动一格）前进，直到遇到非白色格子或越出网格为止，将经过的所有格子涂为蓝色。 现在你可以执行两次 V 字形涂色操作。请计算，两次操作之后，最多能将多少个格子涂成蓝色。 例如，在如下的 $5$ 行 $11$ 列网格中，  第一次在 $(5,5)$ 位置执行 V 字形涂色后，部分格子被涂为蓝色；  第二次在 $(5,9)$ 执行 V 字形涂色后，共有 $11$ 个格子变成蓝色。  而若先在 $(5,9)$ 执行，再在 $(5,5)$ 执行，共有 $13$ 个格子变为蓝色，这比前一种情况更多。  因此，这种情况下的答案是 $13$。

第一行输入两个整数 $N$ 和 $M$，用空格隔开。 接下来的 $N$ 行，每行包含一个长度为 $M$ 的仅由 $0$ 和 $1$ 组成的字符串，表示网格信息。 第 $i$ 行第 $j$ 个字符为 $1$ 表示该格子为白色，为 $0$ 表示为黑色。

输出一个整数，表示两次 V 字形涂色后最多能变成蓝色的格子数量。

**约束条件** - $1 \leq N, M \leq 3000$ - 网格中至少存在 $2$ 个白色格子 **子问题** 1. （11 分）$N, M \leq 20$ 2. （20 分）$N, M \leq 100$ 3. （24 分）$N, M \leq 500$ 4. （45 分）无附加限制条件 翻译由 ChatGPT-4o 完成