关键词：
这题转化一下，就是弄出个01串，然后问最少可以分割成多少个01串
怎么求？贪心策略，如果当前全是0结尾串，又来了一个0，那么只能又多了一个0结尾串，如果来的是1，那么就少了个0结尾串，多了个1结尾串
看了下正解貌似是求最大子段和。。
#include<bits/stdc++.h> using namespace std; #define N 4000005 int n,p,ans; char a[N],b[N],s[N]; void solve() int tot1=0,tot0=0; for(int i=1;i<=p;i++) if(s[i]==‘0‘) if(tot1)tot1--,tot0++; else tot0++; else if(tot0)tot1++,tot0--; else tot1++; ans=max(ans,tot1+tot0); int main() cin>>n; cin>>(a+1)>>(b+1); int x,y; x=y=0; for(int i=1;i<=n;i++) if(a[i]==‘1‘)x++; if(b[i]==‘1‘)y++; if(x!=y)puts("-1");return 0; for(int i=1;i<=n;i++) if(a[i]!=b[i])s[++p]=a[i]; solve(); cout<<ans<<‘ ‘;
最大子段和之环形问题(代码片段)
环形最大子段和题目模型把模型一的线性变成环形。有一个修改，不允许区间为空。问题分析方法一：环形数组的连续最大子段和，有两种情况。最大和的这个子段没有包含头尾。此时跟线型一样。定义dp[i]表示以a[i]结尾的最大... 查看详情
线段树维护区间最大子段和(代码片段)
...什么东西怎么合并如果有区间修改，怎么打标记对于区间最大子段和，我们可以记录四个值：以维护的区间左端点为起点的最大子段和，以维护的区间右端点为终点的最大子段和，在维护区间内的最大子段和和维护区间所有元素... 查看详情
最大子段和之m子段和(代码片段)
最大M子段和题目模型N个整数组成的序列(a_1,a_2,a_3,…,a_n)，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。问题分析方法一：看到序列，我们首先要尝试用线性dp去处理，线性dp经典状态定义:f[i][j]，i一般表示... 查看详情
最大子段和之可交换(代码片段)
可交换的最大子段和题目模型(n)个整数组成的序列(a_1,a_2,...,a_n)，你可以对数组中的一对元素进行交换，并且交换后求(a_1)至(a_n)的最大子段和，所能得到的结果是所有交换中最大的。当所给的整数均为负数时和为0。例如：(-2,11,-... 查看详情
动态规划最大子段和(代码片段)
...ax)nMax=sum; 通过观察发现。(1)整个序列都是负数，那么最大子段和为 最小的负数 。(2)如果都是正数，那么最大子段和就是整个序列的的和。(3)如果有正有负，那么最大的子段和>=整个序列的最大值， ... 查看详情
1049最大子段和(代码片段)
1049 最大子段和 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数... 查看详情
最大子段和(代码片段)
...序列，a[1....n]，求[1,n]某个子区间[i,j]使得a[i]+.....+a[j]和最大，或者求出最大的这个和。例如（-2,11,-4,13,-5,2）的最大子段和为20，所求子区间为[2,4]。 二.问题分析1.穷举法用两层for循环遍历所有的子区间。//穷举法#include<bits... 查看详情
最大子段和dp前缀和c.increasesubarraysums(代码片段)
题目链接：https://codeforces.com/contest/1644/problem/Cf(k)f(k)f(k)表示对一个数组中不同的k个元素做加x操作，最后的最大字段和。求f(0),f(1),...,f(n)f(0),f(1),...,f(n)f(0),f(1),...,f(n)对数组a做前缀和状态表示：f[i−j+1]f[i-j&# 查看详情
51nod1050循环数组最大子段和环形dp/最大子段和/正难则反(代码片段)
1050 循环数组最大子段和基准时间限制：1 秒空间限制：131072 KB分值: 10 难度：2级算法题 收藏 关注N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值... 查看详情
最大m子段和(代码片段)
参考自：最大m子段和总结与例题51nod1052HDU1024 题目介绍：给定由n个整数（可能为负）组成的序列a1、a2、a3...,an,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和最大！特别注意：有些题目可能不存在负... 查看详情
[poj1050]tothemax(最大子段和)(代码片段)
题目链接http://poj.org/problem?id=1050题意求最大子矩阵和。题解即求二维的最大子段和。二维数组sumRec[I][j]存储原始数组数据rec[0][j]torec[I][j]。那么sum[k][j]-sum[I][j]即表示从I+1到k行的第j列这一列的元素和。然后再遍历j，就变成了求一... 查看详情
动态最大子段和(代码片段)
#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e5+10;inlineintread()intx=0,f=1;charch;doch=getchar();if(ch==‘-‘)f=-1;while(!isdigit(ch));dox=x*10+ch-‘0‘;ch=getchar();while(isdigit(c 查看详情
算法竞赛进阶指南扩展最大子段和poj1050tothemax(代码片段)
最大子段和最大子段和可以利用贪心/DP的思想来解决，我这里没有严格证明，但是思考之后觉得很有道理，如果某一段字段和，不包括该数时，前段小于0，能么加上该数不会变的更大，能么当前子段和应该只有当前一个数字，... 查看详情
最大子段和之带长度限制(代码片段)
带长度限制的最大子段和题目模型一个整数序列(a_1,a_2,……,a_n)，求最大的长度不超过K的子段的数值和。问题分析求以a[i]结尾的最大子段和，我们需要维护一个最小的前缀sum[j]，即[j+1,i]为所求。但要求子段和区间长度不能大于K... 查看详情
3981动态最大子段和(代码片段)
...。接下来q次查询，每次动态指定两个数l,r，求a[l]到a[r]的最大子段和。子段的意思是连续非空区间。输入描述 InputDescription第一行一个数n。第二行n个数a[1]~a[n]。第三行一个数q。以下q行每行两个数l和r。输出描述 OutputDescr... 查看详情
codevs3981动态最大子段和（线段树）(代码片段)
题目传送门：codevs3981动态最大子段和 题目描述 Description题目还是简单一点好... 有n个数，a[1]到a[n]。接下来q次查询，每次动态指定两个数l,r，求a[l]到a[r]的最大子段和。子段的意思是连续非空区间。输入描述 ... 查看详情
p1115最大子段和(代码片段)
--------------------------------这就是道普及，也没啥好讲的 主要就是有两个毒瘤数据点 （一个是全正数，一个是全负数）---------------------------------- 题目链接：STF ---------------------------------看了题就会发现挺简单的，DP... 查看详情
p1115最大子段和(线段树)(代码片段)
题目描述-->p1115最大子段和虽然是一个普及-的题,但我敲了线段树qwq数组定义(lsum[])代表该区间左端点开始的最大连续和.(rsum[])代表该区间右端点开始的最大连续和.(ssum[])代表区间内最大连续和.(sum[])代表区间和.QueandAQ:已知一个... 查看详情