1 条题解

  • 0
    @ 2025-6-2 16:40:03
    #include <bits/stdc++.h>
    using namespace std;
    int e[512345][2];
    int tot = 0;
    string s;
    //dp_max[i][j] 节点 i 染成 j 色后,最多多少个绿。
    //0 绿、1 红、2 蓝、
    int dp_max[512345][3];
    int dp_min[512345][3];
    void dfs_build(int now)
    {
        tot++;
        if (s[now - 1] == '1')
        {
            e[now][0] = tot + 1;
            dfs_build(tot + 1);
        }
        if (s[now - 1] == '2')
        {
            e[now][0] = tot + 1;
            dfs_build(tot + 1);
            e[now][1] = tot + 1;
            dfs_build(tot + 1);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> s;
        dfs_build(1);
        for (int i = tot; i >= 1; i--)
        {
            int l = e[i][0];
            int r = e[i][1];
            if (!l)
            {
                dp_max[i][0] = dp_min[i][0] = 1;
                dp_max[i][1] = dp_min[i][1] = 0;
                dp_max[i][2] = dp_min[i][2] = 0;
            }
            else if (!r)
            {
                dp_max[i][0] = max(dp_max[l][1], dp_max[l][2]) + 1;
                dp_max[i][1] = max(dp_max[l][0], dp_max[l][2]);
                dp_max[i][2] = max(dp_max[l][0], dp_max[l][1]);
                dp_min[i][0] = min(dp_min[l][1], dp_min[l][2]) + 1;
                dp_min[i][1] = min(dp_min[l][0], dp_min[l][2]);
                dp_min[i][2] = min(dp_min[l][0], dp_min[l][1]);
            }
            else
            {
                dp_max[i][0] = max(dp_max[l][1] + dp_max[r][2], dp_max[l][2] + dp_max[r][1]) + 1;
                dp_max[i][1] = max(dp_max[l][0] + dp_max[r][2], dp_max[l][2] + dp_max[r][0]);
                dp_max[i][2] = max(dp_max[l][0] + dp_max[r][1], dp_max[l][1] + dp_max[r][0]);
                dp_min[i][0] = min(dp_min[l][1] + dp_min[r][2], dp_min[l][2] + dp_min[r][1]) + 1;
                dp_min[i][1] = min(dp_min[l][0] + dp_min[r][2], dp_min[l][2] + dp_min[r][0]);
                dp_min[i][2] = min(dp_min[l][0] + dp_min[r][1], dp_min[l][1] + dp_min[r][0]);
            }
        }
        cout << max(max(dp_max[1][0], dp_max[1][1]), dp_max[1][2]) << " " << min(min(dp_min[1][0], dp_min[1][1]), dp_min[1][2]) << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    3397
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    2
    已通过
    2
    上传者