要求壁画必须相连,因为要求出最大的美观总分,所以我们不用考虑每天毁坏的是哪一块,只需要考虑选取哪几块就好了,此时很显然用前缀和
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t; cin >> t;
for(int i=1;i<=t;i++) {
int n; cin>>n;
int cnt=(n+1)/2; //可绘制cnt块壁画,注意不是n/2,而是(n+1)/2
long long int a[n+1];
string s;
cin >> s;
for (int j = 1;j <= n;j++) {
a[j] = s[j - 1] - '0';
a[j] += a[j - 1];
}
long long int sum = 0;
for (int j = 1;j + cnt - 1 <= n;j++) {
sum = max(sum, a[j + cnt-1] - a[j-1]);
}
cout << "Case #" << i << ": " << sum;
cout << endl;
}
return 0;
}