工体商城网站建设,做网站设计好的公司,用jsp做的网站框架,企业信息查询系统官网广东1.题目说明
Thanh 想在一面被均分为 N 段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分#xff0c;这表示它的美观程度#xff08;如果它的上面有画的话#xff09;。
不幸的是#xff0c;由于洪水泛滥#xff0c;墙体开始崩溃#xff0c;所以他需要加快他的作画…1.题目说明
Thanh 想在一面被均分为 N 段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分这表示它的美观程度如果它的上面有画的话。
不幸的是由于洪水泛滥墙体开始崩溃所以他需要加快他的作画进度
每天 Thanh 可以绘制一段墙体。
在第一天他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天他只能选择与绘制完成的墙面相邻的墙段进行作画因为他不想分开壁画。
在每天结束时一段未被涂颜料的墙将被摧毁Thanh 使用的是防水涂料因此涂漆的部分不能被破坏且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh想要保证无论墙壁是如何被摧毁的他都可以达到至少 B 的美观总分。
请问他能够保证达到的美观总分 B 的最大值是多少。
2.输入格式
第一行包含整数 T表示共有 T 组测试数据。
每组数据的第一行包含整数 N。
第二行包含一个长度为 N 的字符串字符串由数字 0∼9 构成第 i 个字符表示第 i 段墙面被上色后能达到的美观评分。
3.输出格式
每组数据输出一个结果每个结果占一行。
结果表示为 Case #x: y其中 x 为组别编号从 1 开始y 为 Thanh 可以保证达到的美观评分的最大值。
4.数据范围
1≤T≤100, 存在一个测试点N5∗10的6次方,其他测试点均满足2≤N≤100
5.输入样例
4 4 1332 4 9583 3 616 10 1029384756
6.输出样例
Case #1: 6 Case #2: 14 Case #3: 7 Case #4: 31
7.代码
#includeiostream
using namespace std;
const int N 5000010;
int t,s[N];
char str[N];
int main(){scanf(%d,t);for(int cases 1;cases t;cases){int n;scanf(%d,n);scanf(%s, str 1);//前缀和数组for (int i 1; i n; i )s[i] s[i - 1] str[i] - 0;//用区间长度的尾部开始直到遍历结束找出所有区间里的最大值。int res 0, m (n 1) / 2;for (int i m; i n; i )res max(res, s[i] - s[i - m]);printf(Case #%d: %d\n, cases, res);}return 0;
}
