题目描述
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∗106
,其他测试点均满足2≤N≤100
样例
输入样例:
4
4
1332
4
9583
3
616
10
1029384756
输出样例:
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
C++ 代码
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
int T;
const int N=5e6+10;
char str[N];
int res[N];
int an;
int q=1;
int main()
{
cin >> T;
while(T--)
{
int n;
cin >> n;
cin >> str+1;
for(int i=n;i>0;i--)
{
res[i]=str[i]-'0';//处理字符串
}
for(int i=1;i<=n;i++)res[i]=res[i]+res[i-1];//前缀和
for(int i=n,j=n/2;j>=0;j--,i--)
{
an=max(an,res[i]-res[j]);//每次仅能毁掉两边的壁画,找最大值。
}
cout <<"Case #"<<q++<<":"<<" "<<an;
cout << endl;
an=0;
}
}