原题链接：562. 壁画 - AcWing题库
Thanh 想在一面被均分为 N 段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分，这表示它的美观程度（如果它的上面有画的话）。
不幸的是，由于洪水泛滥，墙体开始崩溃，所以他需要加快他的作画进度！
每天 Thanh 可以绘制一段墙体。
在第一天，他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天，他只能选择与绘制完成的墙面相邻的墙段进行作画，因为他不想分开壁画。
在每天结束时，一段未被涂颜料的墙将被摧毁（Thanh 使用的是防水涂料，因此涂漆的部分不能被破坏），且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh想要保证，无论墙壁是如何被摧毁的，他都可以达到至少 B 的美观总分。
请问他能够保证达到的美观总分 B 的最大值是多少。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据的第一行包含整数 N。
第二行包含一个长度为 N的字符串，字符串由数字 0∼9 构成，第 i 个字符表示第 i段墙面被上色后能达到的美观评分。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为 Thanh 可以保证达到的美观评分的最大值。
数据范围
1≤T≤100 存在一个测试点N=5∗10^6,其他测试点均满足2≤N≤100。
输入样例：
代码语言：javascript复制4
4
1332
4
9583
3
616
10
1029384756输出样例：
代码语言：javascript复制Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31样例解释
在第一个样例中，无论墙壁如何被破坏，Thanh都可以获得 6 分的美观总分。在第一天，他可以随便选一个美观评分3的墙段进行绘画。在一天结束时，第一部分或第四部分将被摧毁，但无论哪一部分都无关紧要。在第二天，他都可以在另一段美观评分 3 的墙段上作画。
在第二个样例中，Thanh 在第一天选择最左边的美观评分为 9 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体，因为最左边的墙壁被涂上了颜料。在第二天，他可以选择在左数第二段评分为 5 的墙面上作画。然后右数第二段墙体被摧毁。请注意，在第二天，Thanh不能选择绘制第三段墙面，因为它不与任何其他作画墙面相邻。这样可以获得 14 分的美观总分。
解题思路：
这个题直接利用枚举和前缀和即可解决，里面有一点思维转化。这个题无非就是寻找连续最大值，既要在洪水来前选择最大值，又要保证画的连续。先来看洪水咋损坏墙，上面题中标粗了，只能与一段未被摧毁的墙相连，那不就是洪水每次从两边损坏墙就可以满足，也只有这样才能满足这个条件，假设洪水足够聪明，每一次去找最大值的墙，万一再墙中央，损坏的两边都相邻着未被损坏的墙，不满足题意。我可以先任选一个，洪水损坏一个，选一个，洪水损坏一个，礼尚往来，那我跟洪水画的（损坏的）是几乎一样的，当n为奇数时我会多画一个，偶数时，我跟洪水画的一样多，那我花的长度就是n/2的上取整，这个题不就迎刃而解了嘛，在这个字符区间上，我利用一个长度为n/2上取整的滑动窗口，从小到大跑一遍，寻找最大值即可。上代码！
代码语言：javascript复制#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e6 5;
int T,n,t;//T组数据，n面墙，t为数据下标用于打印
char ch[N];
int presum[N];//利用前缀和求更快
int main(){
cin>>T;
while(T--){
t;//每次进来下标加一打印case
cin>>n;
int maxx=0;
for (int i = 1; i <=n; i ){
cin>>ch[i];
presum[i]=presum[i-1] ch[i]-'0';//输进来字符型-'0'转化数值型
}
int m=(n 1)/2;//可以最多画m面墙
for(int i=m;i<=n;i ){//连续性遍历m面墙
maxx=max(maxx,presum[i]-presum[i-m]);//寻找最大值
}
cout<<"Case #"<<t<<": "<<maxx<<endl;
}
return 0;
}题目思路打开了就比较简单，关键是思路转化为窗口滑动那一步，文章尚有不足，若有不足，请大家指出，一起加油冲刺蓝桥杯！
