Kick Start 2019

题意

初始时有n面未被粉刷的墙。每次粉刷一堵与已经粉刷过的墙相邻的墙，然后毁坏一堵当前尚未毁坏的墙中最左边或最右边的一堵墙。第一回合可以开始于任意位置。当所有墙均被粉刷或毁坏时结束。每粉刷一堵墙可以获得相应得分。求最大得分。

$n<=5*10^6$

思路

模拟几组数据可以发现，被选择的数字永远是连续的，且不管如何选择，总有一半（向上取整）的数字可以被选。
所以这个问题就被转化成了给定长度的连续和最值问题。

代码

（思考脸：万能AC句“TLE到底是因为我写的丑还是我长得丑?? ”）

 1 const int N=5000100;
 2 int n;
 3 int s[N];
 4 char str[N];
 5 //TLE到底是因为我写的丑还是我长得丑?? 
 6 int main()
 7 {
 8     int T=read();
 9     F(Case,1,T){
10         n=read();
11         memset(s,0,sizeof(s));
12         scanf("%s",str+1); 
13         s[1]=str[1]-'0';
14         int x,mx=0,len=strlen(str+1);//注意str+1 
15         F(i,2,len) s[i]=s[i-1]+str[i]-'0';
16         s[0]=0;
17         F(i,1,n/2+1){
18             if(s[i+(n+1)/2-1]-s[i-1]>mx) mx=s[i+(n+1)/2-1]-s[i-1];
19         }
20         printf("Case #%d: %d
", Case, mx);
21     }
22     return 0;
23 }