本文主要是介绍Contest1002 - HHU ACM 综合训练1 A题 Kingdom of Black and White（朴素），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定一串01序列，序列的值表示为序列中连续的0或1的个数的平方相加的和。最多可以改变其中一个数字变为0或1，求序列最大值。
思路：很朴素的想法，一开始我以为有什么简便算法，然而并没有= =
首先离散化，数组存储的是连续的0或1的个数，之后对这个数组进行遍历，每次把a[i]+1的平方+a[i+1]-1的平方计算出来的和与a[i]的平方+a[i+1]的平方计算出来的和相比较，若更新后的值大，则更新最大差值。a[i]若为1则需要将a[i]左右相加求平方和并与之前的平方和比大小，依旧需要判断之后更新最大差值。
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
long long a[100005]; int main(){ int t; //freopen("test.in","r",stdin) ; cin>>t; for(int i=1;i<=t;i++){ int cnt=0; memset(a,0,sizeof(a)); string s; cin>>s; long long sum=0; for(int j=0;j<s.length();j++){ if(j==0) a[cnt]++; else{ if(s[j]==s[j-1]) a[cnt]++; else{ cnt++; a[cnt]=1; } } } for(int j=0;j<=cnt;j++) sum+=a[j]*a[j]; //cout<<sum<<endl; long long maxn=0; for(int j=0;j<=cnt;j++){ if(a[j]==1){ if(j==cnt){ long long NEW = (a[j-1]+1)*(a[j-1]+1); long long OLD = a[j-1]*a[j-1]+1; if(NEW>OLD){ maxn = max(maxn,NEW-OLD); } } else if(j==0){ long long NEW = (a[j+1]+1)*(a[j+1]+1); long long OLD = 1+a[j+1]*a[j+1]; if(NEW>OLD){ maxn = max(maxn,NEW - OLD); } } else{ long long NEW = (a[j-1]+a[j+1]+1)*(a[j-1]+a[j+1]+1); long long OLD = a[j-1]*a[j-1]+1+a[j+1]*a[j+1]; if(NEW>OLD){ maxn = max(maxn,NEW - OLD); } } } } for(int j=0;j<cnt;j++){ long long NEW = (a[j]+1)*(a[j]+1)+(a[j+1]-1)*(a[j+1]-1); long long OLD = a[j]*a[j]+(a[j+1])*(a[j+1]); if(NEW>OLD){ maxn=max(maxn,NEW-OLD); } } sum+=maxn; printf("Case #%d: ",i); cout<<sum<<endl; } return 0;
}
这篇关于Contest1002 - HHU ACM 综合训练1 A题 Kingdom of Black and White（朴素）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
