P2679 子串

段数之外还要记录当前段是否贴着当前位置

问题

P2679 子串
从字符串 $A$ 中选择恰好 $k$ 个互不重叠的非空子串，按原顺序拼接后得到字符串 $B$。选择位置不同视为不同方案，求方案数对 $10^9+7$ 取模后的结果。

数据规模：$1\le n\le1000$，$1\le m\le200$，$1\le k\le m$。

最开始的状态只记录处理到 $A_i$、已经匹配 $B$ 的前 $j$ 位、使用 $t$ 段。但是这个状态无法判断下一次选择 $A_{i+1}$ 是继续当前段，还是在断开以后新开一段，说明缺少了影响转移的状态信息。

因此增加一维状态：0 表示当前 $A_i$ 没有被选，1 表示 $A_i$ 被选并且是当前最后一段的末尾。跳过 $A_i$ 时，$B$ 的匹配长度与段数都不变；$B_j$ 不能被跳过，它必须由某个真实选择的 $A_i$ 产生。

当 $A_i=B_j$ 时，状态 1 有三个来源：继续上一段；上一位没选并新开一段；上一位被选但在相邻位置主动切开，再新开一段。

于是就可以得到下面这版四维的 DP：

▶

未滚动的四维 DP

ll f[maxn][maxm][maxk][2];
string A, B;

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    cin >> A >> B;
    A = ' ' + A, B = ' ' + B;

    f[0][0][0][0] = 1;
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 0; j <= m; ++ j ) {
            for( int t = 0; t <= k; ++ t ) {
                f[i][j][t][0] = 
                    ( f[i-1][j][t][0] 
                    + f[i-1][j][t][1] ) % mod;
                if( j >= 1 && t >= 1 && A[i] == B[j] ) {
                    f[i][j][t][1] = 
                        ( f[i-1][j-1][t][1] 
                        + f[i-1][j-1][t-1][0]
                        + f[i-1][j-1][t-1][1] ) % mod;
                }
            }
        }
    }
    printf( "%lld\n", f[n][m][k][0] + f[n][m][k][1] );

}

由于状态空间太大了，于是滚动掉 $i$ 这一维。

▶

P2679

ll f[maxm][maxk][2];
ll nf[maxm][maxk][2];
string A, B;

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    cin >> A >> B;
    A = ' ' + A, B = ' ' + B;

    f[0][0][0] = 1;
    for( int i = 1; i <= n; ++ i ) {
        memset( nf, 0, sizeof nf );
        for( int j = 0; j <= m; ++ j ) {
            for( int t = 0; t <= k; ++ t ) {
                nf[j][t][0] = ( f[j][t][0] + f[j][t][1] ) % mod;
                if( j >= 1 && t >= 1 && A[i] == B[j] ) {
                    nf[j][t][1] = ( f[j-1][t][1] + f[j-1][t-1][0] + f[j-1][t-1][1] ) % mod;
                }
            }
        }
        memcpy( f, nf, sizeof nf );
    }
    printf( "%lld\n", ( f[m][k][0] + f[m][k][1] ) % mod );

}