题目
点这里看题目。
分析
插头 DP ，考虑枚举一下两块之间的分割线，本质上就是两个端点都在边界上的路径。
DP 过程中，我们将没有端点在边界上面的路径称为 1 路径，反之叫 2 路径。
对于 1 路径，我们不能中途把它连成环，因此 1 路径的插头需要用括号序表示（最小整数也可以，只要能判掉连通性就可以了）。
接着对插头分一下类：
1.一条 1 路径的左端点，编号为 1 。
2.一条 1 路径的右端点，编号为 2 。
3.一条 2 路径的一个端点，编号为 3 。（如果有 3 插头，那么这个 2 路径的另一个端点就在边界上）
由于插头只有 4 种情况，因此我们使用 4 进制来压缩状态。
另外，我们只能在边界上放(2)个端点，因此需要再开一维来记录一下。
DP 状态如下：
(f(i,j,S,c))：格子((i,j))的轮廓线状态为(S)，并且在边界上放了(c)个端点的方案数。
转移嘛......写起来相当复杂，但是分类讨论本身不难想，所以想看就去代码里找吧qwq逃了。
代码
#include <cstdio>
#include <cstring>
#define l j - 1
#define u j
#define d j - 1
#define r j
#define mov( x ) ( x << 1 )
#define mp( x ) grid[x.first][x.second]
const int MAXN = 20, MAXM = 20, MAXS = ( 1 << 20 ) + 5;
//空间开大，不太清楚为什么qwq
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' );
}
struct table
{
int f[MAXS], stk[MAXS], siz;
table() { memset( f, 0, sizeof f ), memset( stk, 0, sizeof stk ), siz = 0; }
int operator [] ( const int indx ) const { return f[stk[indx]]; }
int operator () ( const int indx ) const { return stk[indx]; }
void add( int S, int v ) { if( ! f[S] ) stk[++ siz] = S; f[S] += v; }
void clear() { while( siz ) f[stk[siz --]] = 0; }
};
struct DP_Structure
{
table F[3];
table& operator [] ( const int indx ) { return F[indx]; }
void clear() { for( int i = 0 ; i < 3 ; i ++ ) F[i].clear(); }
}dp[2];
int stk[MAXM] = {}, top;
int state[MAXM], matched[MAXM];
int grid[MAXN][MAXN];
int N, M, pre = 1, nxt = 0;
void prepare() { pre ^= 1, nxt ^= 1, dp[nxt].clear(); }
int get( int x, int y ) { return ( x >> mov( y ) ) & 3; }
int clr( int x, int y ) { return x & ( ~ ( 3 << mov( y ) ) ); }
int reset( int x, int y, int z ) { return clr( x, y ) | ( z << mov( y ) ); }
int dbset( int x, int y, int a, int b = -1 ) { return reset( reset( x, y, a ), y + 1, ~ b ? b : a ); }
void match()
{
for( int i = 0 ; i <= M ; i ++ )
{
if( state[i] == 1 ) stk[++ top] = i;
if( state[i] == 2 ) matched[stk[top]] = i, matched[i] = stk[top --];
}
}
int encode( int *sta )
{
int ret = 0;
for( int i = M ; ~ i ; i -- ) ret = ( ret << 2 ) + sta[i];
return ret;
}
void decode( int *sta, int val )
{
memset( sta, 0, MAXM * 4 );
for( int i = 0 ; i <= M ; i ++ ) sta[i] = val & 3, val >>= 2;
match();
}
int main()
{
int S, v, lef, up, mtL, mtU;
read( N ), read( M );
N ++, M ++;
if( N > M ) N ^= M, M ^= N, N ^= M;
for( int i = 2 ; i < N ; i ++ )
for( int j = 2 ; j < M ; j ++ )
grid[i][j] = 1;
for( int i = 2 ; i < M ; i ++ ) grid[1][i] = grid[N][i] = 2;
for( int i = 2 ; i < N ; i ++ ) grid[i][1] = grid[i][M] = 2;
prepare();
dp[nxt][0].add( 0, 1 );
for( int i = 1 ; i <= N ; i ++ )
{
prepare();
for( int c = 0 ; c <= 2 ; c ++ )
for( int k = 1 ; k <= dp[pre][c].siz ; k ++ )
if( ! get( dp[pre][c]( k ), M ) )
dp[nxt][c].add( dp[pre][c]( k ) << 2, dp[pre][c][k] );
for( int j = 1 ; j <= M ; j ++ )
{
prepare();
for( int c = 0 ; c <= 2 ; c ++ )
for( int k = 1 ; k <= dp[pre][c].siz ; k ++ )
{
S = dp[pre][c]( k ), v = dp[pre][c][k];
lef = get( S, l ), up = get( S, u );
if( grid[i][j] == 0 ) { if( ! lef && ! up ) dp[nxt][c].add( S, v ); continue; }
decode( state, S );
if( grid[i][j] == 2 )
{
dp[nxt][c].add( S, v );
if( c == 2 ) continue;
if( i == 1 ) { if( ! lef && ! up ) dp[nxt][c + 1].add( reset( S, d, 3 ), v ); }
if( j == 1 ) { if( ! lef && ! up ) dp[nxt][c + 1].add( reset( S, r, 3 ), v ); }
//在上边界与左边界放端点，会在轮廓线上新增 3 插头
if( i == N )
{
if( lef || ! up ) continue;
if( up == 3 ) dp[nxt][c + 1].add( dbset( S, d, 0 ), v );
else
{
state[matched[u]] = 3, state[u] = 0;
dp[nxt][c + 1].add( dbset( encode( state ), d, 0 ), v );
}
}
if( j == M )
{
if( ! lef || up ) continue;
if( lef == 3 ) dp[nxt][c + 1].add( dbset( S, d, 0 ), v );
else
{
state[matched[l]] = 3, state[l] = 0;
dp[nxt][c + 1].add( dbset( encode( state ), d, 0 ), v );
}
}
//在下边界与右边界放端点，会与已有插头连接；如果已有插头不是 3 插头，就需要考虑 3 插头移动的情况
}
else
{
if( ! lef && ! up ) dp[nxt][c].add( S, v ), dp[nxt][c].add( dbset( S, d, 1, 2 ), v );
if( lef && ! up ) dp[nxt][c].add( S, v ), dp[nxt][c].add( dbset( S, d, 0, lef ), v );
if( ! lef && up ) dp[nxt][c].add( S, v ), dp[nxt][c].add( dbset( S, d, up, 0 ), v );
if( lef && up )
{
mtL = matched[l], mtU = matched[u];
state[d] = state[r] = 0;
if( lef == 3 && up ^ 3 ) state[mtU] = 3;
if( lef ^ 3 && up == 3 ) state[mtL] = 3;
//考虑 3 插头移动的情况
if( lef == 1 && up == 1 ) state[mtU] = 1;
if( lef == 2 && up == 2 ) state[mtL] = 2;
//正常括号转移
if( lef ^ 1 || up ^ 2 ) dp[nxt][c].add( encode( state ), v );
//需要把会连成环的情况判掉
}
}
}
}
}
write( dp[nxt][2][0] ), putchar( '
' );
return 0;
}