| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 2564 | Accepted: 1177 |
Description
Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.
Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.
Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.
Input
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.
Output
Sample Input
7
B
B
F
B
F
B
B
Sample Output
3 3
Hint
#include"iostream"
#include"cstring"
#include"cstdio"
#include"algorithm"
#include"cstdlib"
#include"ctime"
using namespace std;
const int ms=;
int dir[ms];
int f[ms];
int N;
int calc(int K)
{
memset(f,,sizeof(f));
int res=;
int sum=;//f的∑
for(int i=;i+K<=N;i++)
{
if((dir[i]+sum)&)
{
res++;
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 res;
}
void solve()
{
int K=,M=N;
for(int k=;k<=N;k++)
{
int m=calc(k);
if(m>=&&M>m)
{
M=m;
K=k;
}
}
printf("%d %d\n",K,M);
}
int main()
{
scanf("%d",&N);
char str[];
for(int i=;i<N;i++)
{
scanf("%s",str);
if(str[]=='B')
dir[i]=;
else
dir[i]=;
}
solve();
return ;
}
随机推荐
-
[转] Web前端优化之 内容篇
原文网址: http://lunax.info/archives/3090.html Yahoo! 的 Exceptional Performance team 在 Web 前端方面作出了卓越的贡献. ...
-
[转]python下很帅气的爬虫包 - Beautiful Soup 示例
原文地址http://blog.****.net/watsy/article/details/14161201 先发一下官方文档地址.http://www.crummy.com/software/Be ...
-
c函数习记
1,user groups 篇幅 the length of an article; fgetgrent(从指定的文件来读取组格式) 相关related functions;fgetpwent hea ...
-
Linux内存中的Cache真的能被回收么？
在Linux系统中,我们经常用free命令来查看系统内存的使用状态.在一个RHEL6的系统上,free命令的显示内容大概是这样一个状态: [root@tencent64 ~]# free ...
-
第二百三十八天 how can I 坚持
最近睡觉,老是梦到死亡,多么可怕啊.感觉好虚幻. spring事务管理,框架搭建. 看着没多少事,最起来感觉好多啊. 梳理下最近爬过的山,时间久了会忘,反正上周没爬,下雪了. 10月18号-香山,11 ...
-
IIS中使用PUT方法錯誤記錄
在IIS7.5中使用PUT,DELETE方法時會遇到404,405錯誤,特記錄解決辦法:404: 405: 在web.config的system.webServer節點中加入 <modules ...
-
查看Linux里某文件的前面/后面几行中的某一行
如,我想看/etc/profile文件的前5行里的第5行. 则, head -5 /etc/profile | tail -1 管道|啊,很简单,就是把左边命令的结果,作为右边的输入. 如, ...
-
work_1
Github的用户名为heiheitian 教科书:代码大全第2版 重构 一维最大子数组之和: #include<stdio.h>void MaxSumSonArrays(int a[], ...
-
通过request读取所有参数
获取request里的所有参数及参数名(参数名自动获取) - [ Java ] request里有两个方法: 1)request.getParameterMap(); Enumeration en ...
-
Debug Tools
.NET专用调试工具:MDBG .NET的死锁调试工具:ACorns.Debugging WinDBG+SOS(Windows平台下最强DeBug工具,是解决BUG的最后手段)