Codeforce 604C 思维 交替子序列

概述//思维可能就是找规律看谁找的快吧 原题链接：http://codeforces.com/problemset/problem/604/C 题意：给出一个0和1组成的字符串，可以对任意一段进行翻转，0变1，1变0。求翻转后的最长的交替子序列。 补充：交替子序列：相邻元素不同，可以不连续，但要保持原顺序。如，10011011，交替子序列为10101. 思路：无论如何翻转，对于子序列来说，最多增加一个

//思维可能就是找规律看谁找的快吧

原题链接：http://codeforces.com/problemset/problem/604/C

题意：给出一个0和1组成的字符串，可以对任意一段进行翻转，0变1，1变0。求翻转后的最长的交替子序列。

补充：交替子序列：相邻元素不同，可以不连续，但要保持原顺序。如，10011011，交替子序列为10101.

思路：无论如何翻转，对于子序列来说，最多增加一个01或10，所以结果为原来的交替子序列长度加2，再和总长n比较（有可能最长交替子序列就是其本身），取最小值。要找出最长的子序列串，只能翻转不是原来序列里的0和1，因为是0和1互变，翻转区间里原来不交替的翻转后也依然不交替，所以一次只能增加一个01或10。（大佬原话：我想要最长就只能翻转不在最长的01子序列范围内的1个0或1，构成01或10，就可以加二，构成01或10，但是不能超过字符串本来的长度，所以就是min(ct+2,n)//不得不说思路流畅，顺理成章）。

完整代码：

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 100005 char s[N];int main(){    int n,t,ct=1;    scanf("%d%s",&n,&s);    t=s[0]-‘0‘;    for(int i=1;i<n;i++){        if((t^(s[i]-‘0‘))==1){            t=s[i]-‘0‘;            ct++;        }    }    cout<<min(ct+2,n)<<endl;    return 0;}

总结

以上是内存溢出为你收集整理的Codeforce 604C 思维 交替子序列全部内容，希望文章能够帮你解决Codeforce 604C 思维 交替子序列所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。