文章

211

粉丝

1

获赞

1151

访问

41.9k

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

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000005;
int a[maxn];
int dp[maxn];
int main(){
	int n;
	while(cin >> n){
		string str;
		cin >> str;
		int cnt = 0,k = 0;

		for(char ch:str){ //将0转1,1转-1,然后求最大字段和就可得最多的0个数(转为1),再加上1的个数得答案
			if(ch == '0')
				a[k++] = 1;
			else{
				a[k++] = -1;
				cnt++;
			}	
		}	

		dp[0] = a[0];
		int maxx = 0;
		for(int j=1;j<n;j++){
			dp[j] = max(dp[j-1]+a[j],a[j]);
			if(dp[j] > maxx)
				maxx = dp[j];
		}				
		cout << maxx + cnt << endl;
	}	
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发