---
title: "壁画"
created: 2025-11-28
tags:
  - 算法
---

# 壁画

## 题目 [壁画](https://www.acwing.com/problem/content/description/564/)

![[image-10822648.png]]

## 思路分析

每天只能画一幅壁画 且最边上的一面墙会被销毁（只能销毁没被画的）

然后第二天只能画在已经画过的旁边的墙上

所以最后的结果一定是连续的某段的总和

那么就可以想到用前缀和求

怎么控制l和r 因为前缀和要s[r]-s[l-1]

可以发现

5面墙无论怎么画 最后一定是连续的3个被画

4面墙无论怎么画 最后一定是连续的2个被画

3面一定是2 6面一定是3

其实就是 对于偶数面墙n 最后连续的区间len为n/2

对于奇数面墙n 最后连续的区间len长度为n/2+1

那么就锁定了一个窗口大小

答案就直接在l=1，r=len ；r≤n ；l++，r++里面咯

用一个max去更新答案 找到最大的 即可

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=5e6+10;
char a[N];
int s[N];
int T,n,cnt=0;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s[i]=s[i-1]+(a[i]-'0');
        }

        int len;
        if(n%2==0)
            len=n/2;
        else
            len=n/2+1;

        int ans=0;
        for(int l=1,r=len;r<=n;l++,r++)
            ans=max(ans,s[r]-s[l-1]);
        cnt++;
        cout<<"Case #"<<cnt<<": "<<ans<<endl;
    }
    return 0;
}
```

## 同类题型

## 视频讲解

- [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/前缀和/壁画|壁画]]

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/前后指针/品种临近|品种临近]] 🏠 [[00-刷题理模型]] ➡️ [[尽可能使字符串相等|尽可能使字符串相等]]