文章

1

粉丝

0

获赞

5

访问

74

头像
字符串区间翻转 题解:
P1642 杭州电子科技大学/南京大学机试题
发布于2026年3月24日 23:04
阅读数 74

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N = 1e7 + 10;

int dp[N];

int main()
{
    int n;
    string str;

    while(cin >> n >> str)
    {
        // 统计1的数量
        int cnt = 0;
        for (int i = 0; i < n; i ++)
        {
            if (str[i] == '1') cnt ++;
        }

        vector<int> w;

        for (int i = 0; i < n; i ++)
        {
            if (str[i] == '1') w.push_back(-1);
            else w.push_back(1);
        }

        // 计算以i为结尾区间反转的最大收益, 可能为负
        dp[0] = w[0];
        int res = 0; // 最坏情况一个都不不反转,收益为0
        for (int i = 1; i < n; i ++)
        {
            dp[i] = max (dp[i-1] + w[i], w[i]);
            res = max (res, dp[i]);
        }


        cout << cnt + res << endl;

        memset(dp, 0, sizeof(int)*n);
    }
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发