AtCoder-abc130_e 题解

发表于2023-03-23更新于2023-05-03

题目传送门

一道二维线性 dp 题……

在 dp 之前，我们需要明确以下几个东西：

状态的表示，状态转移方程，边界条件跟答案的表示。

状态的表示

dpi,j\mathit{dp}_{i,j} 表示考虑序列 SS 的前 ii 个数字跟序列 TT 的前 jj 个数字有多少对两个子序列的内容相同。

状态转移方程

对于 sis_i 与 tjt_j，有以下两种情况。

1. si=tj1.\space s_i=t_j

那 s1∼sis_1 \thicksim s_i 跟 t1∼tjt_1 \thicksim t_j 的公共子序列有包含 sis_i 跟 tjt_j，包含 sis_i 但不包含 tjt_j，不包含 sis_i 跟 tjt_j，不包含 sis_i 但包含 tjt_j 这 44 种可能。

dpi,j=dpi−1,j+dpi,j−1\mathit{dp}_{i,j} = \mathit{dp}_{i-1,j} + \mathit{dp}_{i,j-1}

2. si≠tj2.\space s_i\ne t_j

那 s1∼sis_1 \thicksim s_i 跟 t1∼tjt_1 \thicksim t_j 的公共子序列有包含 sis_i 但不包含 tjt_j，不包含 sis_i 跟 tjt_j，不包含 sis_i 但包含 tjt_j 这 33 种可能。

dpi,j=dpi−1,j+dpi,j−1−dpi−1,j−1\mathit{dp}_{i,j} = \mathit{dp}_{i-1,j} + \mathit{dp}_{i,j-1} - \mathit{dp}_{i-1,j-1}

边界条件

dpi,0=0  (0≤i≤n)\mathit{dp}_{i,0}=0\;(0\le i\le n)

dp0,j=0  ( 0≤j≤m)\mathit{dp}_{0,j}=0\space \space (\space 0\le j\le m)

答案的表示

dpn,m\mathit{dp}_{n,m}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n, m, s[2005], t[2005], dp[2005][2005];
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); // 优化
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= m; i++) cin >> t[i];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 or j == 0) dp[i][j] = 1; // 初始化
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
            else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod; 
        }
        // 进行 dp
    }
    cout << (dp[n][m] % mod + mod) % mod; // 处理负数
    return 0;
}