AcWing 4421. 暴力做法可过,优化可以用前缀和,假设全部打开,看看能关闭几个
原题链接
困难
#include <iostream>
using namespace std;
const int N = 1010;
int n,r;
int a[N];
int b[N] ={0};
int main()
{
int res = 0;
cin >> n >> r;
for(int i = 1;i <= n;i ++ ) cin >> a[i];
for(int i = 1;i <= n;i ++ )
{
if(a[i])
{
res ++ ;
int j = i;
while(j >= 1 && j >= i - r + 1) b[j] ++ ,j -- ;
j = i + 1;
while(j <= n && j <= i + r - 1) b[j] ++ ,j ++ ;
}
}
for(int i = 1;i <= n;i ++ )
if(b[i] == 0)
{
cout << "-1" << endl;
return 0;
}
//for(int i = 1;i <= n;i ++ ) cout << b[i];
for(int i = 1;i <= n;i ++ )
{
bool flag = true;
if(a[i])
{
int j = i;
if(b[j] - 1 <= 0)
{
flag = false;
continue;
}
while(j >= 1 && j >= i - r + 1)
{
if(b[j] - 1 <= 0)
{
flag = false;
break;
}
j -- ;
}
j = i + 1;
while(j <= n && j <= i + r - 1)
{
if(b[j] - 1 <= 0)
{
flag = false;
break;
}
j ++ ;
}
if(flag)
{
res -- ;
for(j = max(0,i - r + 1);j <= min(n,i + r - 1);j ++ ) b[j] -- ;
}
}
}
cout << res;
return 0;
}