bluecode-【米小游】20250329_2_最大面积

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB
难度：中等
出题人：root

描述

给定一个长度为 n 的二进制字符串 s，由 0 和 1 字符组成。我们需要构建一个行数为 n，列数为 n 的方表，由 0 和 1 字符组成。第一行为原始字符串 s，第二行为字符串 s 向右循环移动一个，第三行为字符串 s 向右循环移动两个，以此类推。

求表中所有由 0 组成的三角形或矩形的最大面积值。

第一行是字符串 s。
第二行是字符串 s 向右循环移动一个位置。
第 i 行是字符串 s 向右循环移动 i-1 个位置。

输入描述

输入一个长度为 n 的二进制字符串 s，仅包含 0 和 1 字符，其中 1 < n < 5000。

输出描述

输出表中所有由 0 组成的三角形或矩形的最大面积值。

用例输入 1 

00110

用例输出 1 

6

提示

样例1说明

在构造的方表中，最大由 0 组成的矩形面积为 6，构造的表格如下：
00110
00011
10001
11000
01100

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::string input;
    std::cin >> input;
    std::vector<int> s;
    for (char c : input) {
        s.push_back(c - '0');
    }
    int n = s.size();

    if (std::find(s.begin(), s.end(), 1) == s.end()) {
        std::cout << n * n << std::endl;
    } else {
        int ed = n - 1;
        while (ed > 0 && s[ed] == 0) {
            ed--;
        }

        std::vector<int> rotated_s(s.begin() + ed, s.end());
        rotated_s.insert(rotated_s.end(), s.begin(), s.begin() + ed + 1);

        int cnt = 0;
        int cur = 0;
        for (int c : rotated_s) {
            if (c == 0) {
                cur++;
            } else {
                cur = 0;
            }
            cnt = std::max(cnt, cur);
        }

        // 三角形
        int res = cnt * (1 + cnt) / 2;

        // 矩形
        for (int k = 1; k <= cnt; k++) {
            int m = cnt - (k - 1);
            res = std::max(res, k * m);
        }

        std::cout << res << std::endl;
    }
    return 0;
}