首页 > 代码库 > [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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。