KickStart-RoundH-ProblemB-Mural

本文主要是介绍KickStart-RoundH-ProblemB-Mural，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目大意:小明要在连续的N面墙上画画，每面墙画好之后都能得到相应的分数，但是由于天气不好有洪水，每天都会毁掉一面墙，因此小明找找出能得到最高分数的画画方案。
注：小明第一次画画时可以随意选择一面墙开始，但是接下来的每一天，他只能画他已画过的部分旁边的新部分。在每一天结束的时候，洪水都会毁掉一面墙，这面墙是没有被画过的且是两头（就是墙的头或者尾部），因为小明用的是防水涂料所以已经画过的部分不会被冲掉。


解题思路：
能画的墙的长度为N/2（取大，即不小于N的最小整数，如3/2=1.5，则取2），无论如何，只要选取了长度为N/2的墙部分，总有办法能把它画完，因此，取窗口大小为N/2的窗口，遍历所有墙面，分数和最大的窗口就是答案。

#include <iostream>using namespace std;int wallScore[10000005];
int score(float N,string wall,int NO){int low=0,high=int(N/2+0.5)-1,MAX=0;for(int i=0;i<N;i++){wallScore[i]=wall[i]-48;}int sum=0;for(int j=low;j<=high;j++){sum+=wallScore[j];}while(high<N){if(sum>MAX){ MAX=sum; }sum=sum-wallScore[low];++low;++high;sum=sum+wallScore[high];}cout<<"Case #"<<NO<<": "<<MAX<<endl;return 0;
}int main()
{int T;float N;string wall;cin>>T;for(int i=1;i<=T;i++){cin>>N>>wall;score(N,wall,i);}return 0;
}

这篇关于KickStart-RoundH-ProblemB-Mural的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---