UVALive 7410 Kingdom of Black and White

题意：

给了你一个01串你只能改变一位问你改变之后该串的最大价值可以是多少

价值的计算方式为每一段的长度的平方加和

思路：

思路就是暴力处理每一段

题是不难但是训练的时候没有做出来

总结一下还是因为没有计算好时间复杂度

本来可以暴力的题加上了莫名的贪心然后就找不出bug了……

所以该暴力的题就要暴力不要总想着优化

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(a) cerr<<#a<<"=="<<a<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int maxn=1e5+10;
 8 
 9 char str[maxn];
10 ll s[maxn];
11 
12 int main()
13 {
14     int T,cas=1;
15     scanf("%d",&T);
16     while(T--)
17     {
18         scanf("%s",str);
19         int len=strlen(str);
20         cl(s,0);
21         ll ans=0,now=1,cnt=1,k=1;
22         for(int i=0;i<len-1;i++)
23         {
24             if(str[i]!=str[i+1])
25             {
26                 s[cnt]=k;
27                 ans+=k*k;
28                 k=1;
29                 cnt++;
30             }
31             else
32             {
33                 k++;
34             }
35         }
36         ans+=k*k;
37         s[cnt]=k,now=ans,cnt++;
38         for(int i=1;i<cnt;i++)
39         {
40             if(s[i]==1)
41             {
42                 ans=max(ans,now-s[i+1]*s[i+1]-s[i-1]*s[i-1]-1+(s[i+1]+s[i-1]+1)*(s[i+1]+s[i-1]+1));
43             }
44             else
45             {
46                 ans=max(ans,now-s[i+1]*s[i+1]-s[i]*s[i]+(s[i+1]+1)*(s[i+1]+1)+(s[i]-1)*(s[i]-1));
47                 ans=max(ans,now-s[i-1]*s[i-1]-s[i]*s[i]+(s[i-1]+1)*(s[i-1]+1)+(s[i]-1)*(s[i]-1));
48             }
49         }
50         printf("Case #%d: %lld
",cas++,ans);
51     }
52     return 0;
53 }/*
54 
55 2
56 000011
57 0101
58 
59 */