codeforces #327 A. Flipping Game

http://codeforces.com/contest/327/problem/A
题意:给定一段序列,只由0,1组成。要求选一段非空区间,做翻转操作(0变1,1变0),问变完之后1最多能有多少。
思路:最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那么我们只要找到某一个区间内,0的个数-1的个数有最大值即可。如果a[i]==0的时候令b[i]=1,否则b[i]=0,那就是经典了最大连续区间和的问题了。dp的思想o(n)可以解决。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz