题目描述
Thanh 想在一面被均分为 N
段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分,这表示它的美观程度(如果它的上面有画的话)。
不幸的是,由于洪水泛滥,墙体开始崩溃,所以他需要加快他的作画进度!
每天 Thanh 可以绘制一段墙体。
在第一天,他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天,他只能选择与绘制完成的墙面相邻的墙段进行作画,因为他不想分开壁画。
在每天结束时,一段墙将被摧毁。被毁掉的墙段一定只与一段还未被毁掉的墙面相邻并且没有涂颜料(Thanh 使用的是防水涂料,因此涂漆的部分不能被破坏)。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh想要保证,无论墙壁是如何被摧毁的,他都可以达到至少 B
的美观总分。
请问他能够保证达到的美观总分 B
的最大值是多少。
样例
输入样例:
4
4
1332
4
9583
3
616
10
1029384756
输出样例:
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
样例解释
在第一个样例中,无论墙壁如何被破坏,Thanh都可以获得 6
分的美观总分。在第一天,他可以随便选一个美观评分3的墙段进行绘画。在一天结束时,第一部分或第四部分将被摧毁,但无论哪一部分都无关紧要。在第二天,他都可以在另一段美观评分 3
的墙段上作画。
在第二个样例中,Thanh 在第一天选择最左边的美观评分为 9
的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体,因为最左边的墙壁被涂上了颜料。在第二天,他可以选择在左数第二段评分为 5
的墙面上作画。然后右数第二段墙体被摧毁。请注意,在第二天,Thanh不能选择绘制第三段墙面,因为它不与任何其他作画墙面相邻。这样可以获得 14
分的美观总分。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5e6 + 10;
int a[N], s[N];
int check(int s[], int len)
{
int res = 0;
for(int i = 0, j = (len + 1) / 2 ; j <= len ; i ++, j ++)
{
res = max(res, s[j] - s[i]);
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
for(int i = 1 ; i <= T ; i ++)
{
memset(a, 0, sizeof a);
memset(s, 0, sizeof s);
int n;
scanf("%d",&n);
for(int i = 1 ; i <= n ; i ++)
{
char c;
cin >> c;
a[i] = c - '0';
s[i] = s[i-1] + a[i];
}
int res = check(s, n);
printf("Case #%d: %d\n",i,res);
}
return 0;
}