首页 > 代码库 > [HDOJ5791]Two(DP)

[HDOJ5791]Two(DP)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5791

题意:给两个数列,求有多少个公共子序列。

dp(i,j)表示a1~ai和b1~bj的公共子序列个数,当ai==bj的时候,dp(i,j)=dp(i-1,j)+dp(i,j-1)+1。否则dp(i,j)=dp(i-1,j)+dp(i,j-1)-dp(i-1,j-1),这是因为在加两个单独分支的时候重复加了一次dp(i-1,j-1)。但是减完以后可能会是负数,要加一个mod。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const LL mod = 1000000007;
 6 const int maxn = 1010;
 7 int n, m;
 8 int a[maxn], b[maxn];
 9 LL dp[maxn][maxn];
10 int main() {
11     // freopen("in", "r", stdin);
12     while(~scanf("%d%d",&n,&m)) {
13         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
14         for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
15         memset(dp, 0, sizeof(dp));
16         for(int i = 1; i <= n; i++) {
17             for(int j = 1; j <= m; j++) {
18                 if(a[i] == b[j]) {
19                     dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1;
20                     dp[i][j] %= mod;
21                 }
22                 else {
23                     dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
24                     dp[i][j] += mod;
25                     dp[i][j] %= mod;
26                 }
27             }
28         }
29         cout << dp[n][m] << endl;
30     }
31     return 0;
32 }

 

[HDOJ5791]Two(DP)