bzoj1704 / P2882 [USACO07MAR]面对正确的方式Face The Right Way

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

P2882 [USACO07MAR]面对正确的方式Face The Right Way

$n<=5000$？枚举翻转长度，顺序模拟就ok了

对于每次翻转，我们可以利用差分的思想，再搞搞前缀和。

（输出反了还交，真菜）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define N 10010

 int n,a[N],s[N],p[N],ans,mnd=1e9;

 int main(){

     scanf("%d",&n); char q[];

     for(int i=;i<=n;++i)

         scanf("%s",q),a[i]=(q[]=='B');

     for(int i=n,tot,ed;i>=;--i){

         memset(p,,sizeof(p));tot=,ed=;

         for(int j=;j<=n-i+;++j){

             s[j]=s[j-]+p[j];

             if((a[j]+s[j])&)//该位需要翻转

                 ++s[j],--p[j+i],++tot;

         }

         for(int j=n-i+;j<=n&&!ed;++j){

             s[j]=s[j-]+p[j];

             if((a[j]+s[j])&) ed=;//判断剩下的是否有转到前面去

         }

         if(!ed&&tot<=mnd) mnd=tot,ans=i;//更新答案

     }printf("%d %d",ans,mnd);

     return ;

 }