题意:给一个只有0和1的字符串,允许反转一个连续区间,即0变成1,1变成0,求最长的01交替串多长,允许不连续。
我最先想到的是动态规划解法,状态设计方面,首先一个串的状态会有以0结尾和以1结尾两种,然后题目中说允许反转一个连续区间,那么根据反转的前后,可以分为反转前,反转中(最后一个字符是被反转的)和反转后,所以组合起来,状态一共有6种,即反转前0结尾、反转中0结尾(未反转时为0,反转后为1)、反转后0结尾、反转前1结尾、反转中1结尾(未反转时为1,反转后为0)、反转后1结尾,然后每个状态的字符串具体是什么样子我们都可以不用关心,只需要关心每一种状态下长度最长的串是多多长。
然后是状态转移部分。当下一个字符是1时,1可以添加到反转前0结尾的串后面,然后长度加1,得到一个反转前1结尾的串;也可以反转成0添加到反转前1结尾的串后面,得到一个反转中以1结尾的串,以此类推:
下一个字符是0的时候同理:
但是要注意状态跟新的顺序,应该是从右往左更新的。否则的话,如果从左往右更新,一个字符会被计算三遍。
最后就可以得到每种状态下的最长串,然后选出最长的那个就是最后的结果。
最后的最后,此处假装有代码。
/*
笔试的时候代码并没有保存下来,所以此处并没有代码,如果讲的不够清楚的话会补充上
*/