关键在于意识到 按照一种最优策略,每一个区间都可以必被画完。
这个策略就是按照区间两侧外的空墙长度来选择起始位置,然后洪水从哪来就往哪画(可以一会向左一会向右),一定可以画完这个区间。
#include<iostream>
using namespace std;
const int N = 5000010;
int T,n;
int a[N];
int main()
{
cin >> T;
for(int k = 1;k <= T;k++)
{
scanf("%d",&n);
string str;
cin >> str;
for(int i = 1;i <= n;i++) a[i] = str[i-1] - '0',a[i] += a[i-1];
int res = 0,len = (n+1) / 2;
for(int i = len;i <= n;i++) res = max(res,a[i] - a[i-len]);
printf("Case #%d: %d\n",k,res);
}
}
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
typedef long long ll;
const int N = 500010;
int arr[N];
int T;
int n;
int main() {
cin >> T;
int t = 0;
while (t < T) {
cin >> n;
string str;
cin >> str;
for (int i = 1; i <= n; i++) {
arr[i] = str[i - 1] - ‘0’;
arr[i] += arr[i - 1];
}
佬这样会越界吗,为什么我报段错了。求求了,一晚上想不明白
}
N开小了