Kingdom of Black and White （分类讨论）

Kingdom of Black and White （分类讨论）

In the Kingdom of Black and White (KBW), there are two kinds of frogs: black frog and white frog. Now N frogs are standing in a line, some of them are black, the others are white. The total strength of those frogs are calculated by dividing the line into minimum parts, each part should still be continuous, and can only contain one kind of frog. Then the strength is the sum of the squared length for each part. However, an old, evil witch comes, and tells the frogs that she will change the color of at most one frog and thus the strength of those frogs might change. The frogs wonder the maximum possible strength after the witch finishes her job. Input First line contains an integer T, which indicates the number of test cases. Every test case only contains a string with length N, including only 0 (representing a black frog) and 1 (representing a white frog). Restrictions: • 1 ≤ T ≤ 50. • for 60% data, 1 ≤ N ≤ 1000. • for 100% data, 1 ≤ N ≤ 105 . • the string only contains 0 and 1. Output For every test case, you should output ‘Case #x: y’, where x indicates the case number and counts from 1 and y is the answer. Sample Input 2 000011 0101 Sample Output Case #1: 26 Case #2: 10

题目大概：

给你一个01串，然后连续的0或1的个数的平方是这一段串的价值，可以修改一个字符的类型，求串的总价值。

比如例题  000011 价值为20 ---》修改为000001  价值为26

思路：

分两种情况讨论求出最大值。

首先把连续的一段01串都合并为一个数据结构，一起算。

然后连续的两段串，可以把少的串的一个字符修改成多的。计算最大值。

连续三段串，中间串长度为1.可以把三段串连起来，求最大值。

这样两种情况求最大，注意爆long  long

代码：

#includeusing namespace std;#define ll long longconst int maxn=1e5+10;const int INF=0x3f3f3f3f;const int mod=1e9+7;string s;struct node{ ll id,length;} G[maxn];int tem;int main(){ int t; int ans=1; scanf("%d",&t); while(t--) { cin>>s; memset(G,0,sizeof(G)); int l=s.size(); tem=0; int flag=-1; ll sum=0; for(int i=0; i0) { G[tem].id=flag; G[tem++].length=sum; } ll max_1=0; ll sum_1=0; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。