acwing 562 壁画

题意

对一些墙壁进行作画，被作画的墙不会毁掉，只有和一面墙相邻的会被毁掉，每天可以画一面墙，每天画的墙必须和昨天画的相邻，然后会有一面墙被毁掉，每堵墙都有美观分，求使最终剩下的墙美观分能够到达的总和最高的值。

思路

首先只有和一面墙相邻的会被毁掉意思就是从两端开始毁掉，由于每天画一面墙，毁一面墙，那最终是能保留面墙，那么题目就是求长度为的连续序列和的最大值。

然后，我们就需要枚举每个起点，来比较以此为起点的连续序列和。其实循环下去每次减一个头元素，再加一个尾元素也可以。但是这边用前缀和来处理，每个连续序列和的计算公式为，需要注意的是，虽然是以为起点，但是号元素还是需要的，想要获取以为起点的连续序列和，需要减去前面的前缀和。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve(int T)
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    vector<int>sum(n+1);
    for(int i=0;i<str.size();++i){
        sum[i+1]=str[i]-'0';
    }
    for(int i=1;i<=n;++i){
        sum[i]+=sum[i-1];
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        // cerr<<sum[i]<<endl;
        if(i+(n+1)/2-1<=n)ans=max(ans,sum[i+(n+1)/2-1]-sum[i-1]);
    }
    cout<<"Case #"<<T<<": "<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    for(int i=1;i<=T;++i)	solve(i);
    return 0;
}