NC19978 [HAOI2010]最长公共子序列
dp[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列
res[i][j]的含义为s1串的前i长度与s2串的前j长度的最长公共子序列长度为dp[i][j]的数目
如果s1[i][j]==s2[i][j]那么dp[i][j]=dp[i-1][j-1]+1 res[i][j]=res[i-1][j-1]
如果不相等 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); 注意 dp[i][j - 1]和 dp[i - 1][j]都包含了dp[i-1][j-1]的情况,所以如果dp[i][j]==dp[i-1][j-1],res[i][j]应该减去res[i-1][j-1]。
#include <iostream> #include <string.h> using namespace std; const int maxn = 5010; const int mod = 100000000; int dp[maxn][maxn]; int res[maxn][maxn]; char s1[maxn]; char s2[maxn]; int main() { cin >> s1+1 >> s2+1; int n = strlen(s1 + 1) - 1; int m = strlen(s2 + 1) - 1; for (int i = 0; i <= n; i++) res[i][0] = 1; for (int i = 0; i <= m; i++) res[0][i] = 1; int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s1[i] == s2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; res[i][j] = res[i - 1][j - 1]; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); if (dp[i][j] == dp[i - 1][j - 1])res[i][j] = (res[i][j] - res[i - 1][j - 1] + mod) % mod; } if (dp[i][j] == dp[i - 1][j]) res[i][j] += res[i - 1][j]; if (dp[i][j] == dp[i][j - 1]) res[i][j] += res[i][j - 1]; res[i][j] %= mod; } } cout << dp[n][m]<<endl; cout << res[n][m]; }
题解汇总 文章被收录于专栏
无