【问题描述】

一条新建立的笔直的街道上有 n 盏路灯，目前正处于调试阶段。路灯只有亮和不亮两种状态， 现在有些灯亮着、有些不亮。小 y 手里有一个不成熟的调试仪器，使用前必须设定一个数值 K，机 器每操作一次恰好使 K 个连续的路灯状态反转（亮变成不亮、不亮变成亮）。 现在，请你编程求出：为了让所有路灯都不亮需要的最少操作次数 M 和对应的最小 K 值。

【输入】

第 1 行为整数 n。 第 2 行为 n 盏路灯的初始状态，状态用“B”和“F”标记，分别表示亮和不亮。

【输出】

输出 2 行，每行 1 个整数。 第 1 行表示最少的操作次数 M，第 2 行表示最小的 K 值。

【输入样例】

7

BBFBFBB

【输出样例】

3

3

【样例解释】

K=3，先反转 1～3 号，再反转 3～5 号，再反转 5～7 号。

【数据范围】

对于 40%的数据满足：n <= 400。

对于 100%的数据满足：1 <= n <= 4000。

//20分
#include<bits/stdc++.h>
using namespace std;
string st;
queue<int>q;
bool a[50000],dft[50000],used[50000];
int n,m,x,xx,cnt,C,X,minans=0x3f3f3f3f,flag,tot=0,b[50000],c[50000],s[50000],dis[100][100],dp[1000000],ans[4001];
inline void _min(int& x, const int y) {
	x = x > y ? y : x;
}
int main() {
	freopen("rever.in","r",stdin),freopen("rever.out","w",stdout);
	cin>>n>>st;
	for (register int i = 0; i < n; ++i) {
		if(st[i]=='B') {
			a[i+1]=1,tot++;
		}
	}
	if(tot==st.size()) {
		cout<<1<<'\n'<<tot<<'\n';
		return 0;
	}
	for (register int i = 1; i <= n + 1; ++i) {
		dft[i] = a[i - 1] ^ a[i];
		if (dft[i]) c[++cnt] = i;
	}
	for(b[1]=1; b[1]<n; b[1]++) {
		for (register int i = 1; i <= cnt; ++i) {
			for (register int j = 1; j <= n + 1; ++j) s[j] = used[j] = 0;
			used[c[i]] = 1;
			q.push(c[i]);
			while (!q.empty()) {
				x = q.front(),q.pop(),xx = x + b[1];
				if (xx <= n + 1 && !used[xx]) {
					s[xx] = s[x] + 1,used[xx] = 1;
					q.push(xx);
				}
				xx=x-b[1];
				if (xx > 0 && !used[xx]) {
					s[xx] = s[x] + 1,used[xx] = 1;
					q.push(xx);
				}
			}
			for (register int j = 1; j <= cnt; ++j) dis[i][j] = s[c[j]];
		}
		C=1<<cnt;
		for (register int i = 1; i <= C; ++i) dp[i] = 0x3f3f3f3f;
		for (register int i = 0; i <= C; ++i) {
			x = 0,X = 1;
			while (X & i) X *= 2, ++x;
			for (register int j = x + 1, J = 1 << j; j <= cnt; ++j, J *= 2)
				if (!(J & i) && dis[x + 1][j + 1])_min(dp[i | X | J], dp[i] + dis[x + 1][j + 1]);
		}
		ans[b[1]]=dp[C-1];
	}
	for(int q=1; q<n; q++) {
		if(ans[q]<minans) {
			minans=ans[q],flag=q;
		}
	}
	cout<<minans<<'\n'<<flag<<'\n';
}