题目再次链接

题意：

　　已知01序列a，求进行定长子串取反的最少操作次数，以及最少时的定长。

分析：

　　首先，先想一想怎么暴力吧。这样想：要保证最小，那么必然不会对同一个区间反转两次，而在k一定时，则不会以同一个数为起点反转两次，于是我们有如果第一个数是0，则反转，是1，则不反转，第一个是否反转就可以确定了，然后按照反转操作进行反转，反转完之后再判断第二个，一直到最后一个（如果区间后端超了n，那么将不会反转成功），然后我们枚举k找到满足条件的k，以及其反转次数。

　　暴力还是比较简单的，就是枚举+模拟，但是这样的复杂的接受不了。怎么办呢，我们想想可以对哪个环节进行优化，枚举环节好像没啥，该枚举还是要枚举。

　　那模拟环节呢，你会发现，其实我们判断他需不需要改变是1的，只不过是模拟改变的过程还要走一遍k，这是复杂度无法接受的原因，那么我们能不能在保证判断是1的情况下改掉模拟修改的复杂度，当然不一定是模拟，总之要找一种方法记录下来修改保证判断操作是1.

　　其实还是比较好想到的：因为我们在判断i的过程中只需考虑它前面k-1个区间的修改次数，这个就相对好记录了，边判断边记录就可以了，这样维护它被修改的次数的操作也变为1了。问题就迎刃而解了。

代码：

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

const int maxn=+;

bool a[maxn];

int f[maxn];

int sum[maxn];

int Co(int k,int n){

    memset(f,,sizeof(f));

    memset(sum,,sizeof(sum));

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

        bool js=a[i];

        if((sum[i-]-sum[(i-k)>?(i-k):])%)

            js=!js;

        if(js){

            if(i+k->n)

                return -;

            f[i]=;

        }

        sum[i]=f[i]+sum[i-];

    }

    return sum[n];

}

int main(){

    int n;

    scanf("%d",&n);

    char js;

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

        scanf(" %c",&js);

        if(js=='B')

            a[i]=;

    }

    int k;

    int jsjs;

    int ans=1e9;

    int ans2;

    for(k=n;k>=;k--)

        if(jsjs=Co(k,n)+){

            if(jsjs-<ans){

                ans=jsjs-;

                ans2=k;

            }

        }

    printf("%d %d",ans2,ans);

    return ;

}//注释就暂时不写啦

巴特西

Face The Right Way思维。。。

题目再次链接

题意：

分析：

代码：

最新文章

热门文章