HDU 5791 Two——DP

HDU 5791 Two——DP

求两个串的公共子串的个数，LCS变形

#include #include #include #include using namespace std;typedef long long ll;const int MAXN = 1010;const int mod = 1000000007;int N, M, a[MAXN], b[MAXN];ll dp[MAXN][MAXN];int main() { while (~scanf("%d %d", &N, &M)) { for (int i = 1; i <= N; i++) scanf("%d", &a[i]); for (int j = 1; j <= M; j++) scanf("%d", &b[j]); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (a[i] == b[j]) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1; else dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mod; dp[i][j] %= mod; } } printf("%I64d\n", dp[N][M]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。