题目
点这里看题目。
分析
这种问题我们通常可以考虑合法染色方案的等价条件。
一步简单的转化是，将染色看成删除。此时要求就是，如果删除一个孤立的格子且不是最后一个格子，那么其它连续段的两端的颜色必须全部不同于当前格颜色。
基于此，对于合法的染色方案，我们可以尝试构造删除方案：
除了最后一个被删除的段之外，我们总能找到某一个步骤，使得该步骤的状态为：被操作段之外的所有段两端颜色都相同（例如某个段被删除干净的时候）。那么记其余段两端颜色为 (overline{c}) ，记其补色为 (c) 。
那么借助这个机会，我们必然可以让所有包含 (c) 的段全部删掉。剩余的段，就只会包含 (overline{c}) 。可以发现这样的段最多只能有一个，所以它就是最后被删除的段。
上面这个过程我们说明了 " 合法的染色方案必然有一种所述的删除方案 " ，而如果有所述的删除方案，显然该染色方案是合法的。即 " 存在一种所述删除方案 " (Leftrightarrow) " 该染色方案合法 " 。
整理一下，我们可以直接枚举 (c) ，那么有如下限制：
- 对于第一个被删除的段，即最后被染色的段，它必须包含子序列 (c) ；
- 对于中间被删除的段，即中间被染色的段，它和它两边必须包含子序列 (overline{c}coverline{c}) ；
- 对于最后被删除的段，即第一个被染色的段，它和它两边必须包含子序列 (overline{c}overline{c}) ；
知道了限制，我们就可以开始 DP 了。我们可以设状态：
(f(i,0/1,0/1)) ：当 (i) 强制不选时，是否存在最后被删的段，是否存在第一个被删的段，此时的最小覆盖数。
转移的时候，我们可以使用类似于 子序列自动机 的指针迅速定位最近的合法转移点。由于此时的一组前缀都是合法的，所以我们需要用一些辅助变量记录前缀的最小值。
最后，注意只有一段的方案总是合法的，所以需要单独计算只有一段的结果。
小结：
- 构造方案，寻找合法方案的等价条件的思路值得再次强调。
- 贪心的删除思想也是比较巧妙的。
- 寻找条件的过程一定要细致，不要错过任何细小的条件。
代码
#include <cstdio>
#include <cstring>
#define rep( i, a, b ) for( int (i) = (a) ; (i) <= (b) ; (i) ++ )
#define per( i, a, b ) for( int (i) = (a) ; (i) >= (b) ; (i) -- )
const int MAXN = 1e5 + 100;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int fir[2], las[2], nei[2][2];
int tf[MAXN], tl[MAXN], tn[MAXN];
int pre[MAXN][2], dp[MAXN][2][2];
char S[MAXN];
int s[MAXN], t[MAXN];
int N, ans;
void Upt( int &x, const int v ) { x = MIN( x, v ); }
int Pre( const int x, const int c ) { return x <= 0 ? -1 : pre[x][c]; }
void Init()
{
N += 3;
s[1] = 0, s[N - 1] = s[N] = 1;
t[1] = t[N - 1] = t[N] = 0;
int mx = 0, mn = N;
rep( i, 1, N ) if( t[i] )
mx = MAX( mx, i ), Upt( mn, i );
ans = mx - mn + 1;
pre[1][0] = pre[1][1] = -1;
rep( i, 2, N )
pre[i][0] = ( s[i - 1] ? pre[i - 1][0] : i - 1 ),
pre[i][1] = ( s[i - 1] ? i - 1 : pre[i - 1][1] );
}
int Calc( const int c )
{
int _c = c ^ 1;
rep( i, 1, N )
tf[i] = Pre( Pre( i + 1, _c ) - 1, _c ),
tl[i] = Pre( i, c ) - 1,
tn[i] = Pre( Pre( Pre( i + 1, _c ), c ), _c );
memset( dp, 0x3f, sizeof dp );
memset( fir, 0x3f, sizeof fir );
memset( las, 0x3f, sizeof las );
memset( nei, 0x3f, sizeof nei );
dp[0][0][0] = 0;
int pf = 0, pl = 0, pn = 0;
rep( i, 1, N )
{
if( t[i] ) continue;
for( ; pf <= tf[i] ; pf ++ )
rep( k, 0, 1 ) Upt( fir[k], dp[pf][0][k] - pf );
for( ; pl <= tl[i] ; pl ++ )
rep( k, 0, 1 ) Upt( las[k], dp[pl][k][0] - pl );
for( ; pn <= tn[i] ; pn ++ )
rep( j, 0, 1 ) rep( k, 0, 1 )
Upt( nei[j][k], dp[pn][j][k] - pn );
memcpy( dp[i], dp[i - 1], sizeof dp[i - 1] );
Upt( dp[i][0][0], nei[0][0] + i - 1 );
Upt( dp[i][1][0], MIN( nei[1][0], fir[0] ) + i - 1 );
Upt( dp[i][0][1], MIN( nei[0][1], las[0] ) + i - 1 );
Upt( dp[i][1][1], MIN( nei[1][1], MIN( fir[1], las[1] ) ) + i - 1 );
}
return dp[N][1][1];
}
int main()
{
read( N );
scanf( "%s", S + 1 );
rep( i, 1, N ) s[i + 1] = S[i] == 'b';
scanf( "%s", S + 1 );
rep( i, 1, N ) t[i + 1] = S[i] == 'o';
Init();
write( MIN( ans, MIN( Calc( 0 ), Calc( 1 ) ) ) ), putchar( '
' );
return 0;
}