题目:Click here

题意:n头牛排成一列,F表示牛面朝前方,B表示面朝后方,每次转向K头连续的牛的朝向,求让所有的牛都能面向前方需要的最少的操作次数M和对应的最小的K。

分析:一个区间反转偶数次等于没反转,f[i]表示区间[i,i+K-1]是(1)否(0)进行了反转,所以在考虑第i头牛的时候,如果f[i-K+1]+f[i-K]+···+f[i-1]为奇数的话,这头牛的方向与起始的方向是相反的,否则方向没变。

 #include <cstdio>
#include <cstring>
using namespace std;
const int M = 5e3+;
int n;
int dir[M]; // 牛的方向(0:F,1:B)
int f[M]; // 区间[i,i-K+1]是否进行了反转 void input() {
while( ~scanf("%d\n", &n ) ) {
for( int i=; i<n; i++ ) {
char x;
scanf("%c\n", &x );
if( x == 'F' ) dir[i] = ;
else dir[i] = ;
}
}
}
int calc( int k ) { // 对于固定的K,求对应的最小的操作数,无解为-1
memset( f, , sizeof(f) );
int sum = ;
int ret = ; // f的部分和
for( int i=; i+k<=n; i++ ) {
if( (dir[i]+sum)% != ) { // 当前牛面朝后方
ret++;
f[i] = ;
}
sum += f[i];
if( i-k+ >= )
sum -= f[i-k+];
}
for( int i=n-k+; i<n; i++ ) { // 检查剩下的牛的朝向
if( (dir[i]+sum)% != )
return -;
if( i-k+ >= )
sum -= f[i-k+];
}
return ret;
}
void solve() {
int K = , M = n;
for( int i=; i<=n; i++ ) {
int m = calc( i );
if( m < M && m >= ) {
M = m;
K = i;
}
}
printf("%d %d\n", K, M );
}
int main() {
input();
solve();
return ;
}
04-26 16:30