Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 21 Accepted Submission(s): 10
类似最长公共子序列的dp。
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e5 + 10; ll a[maxn], b[maxn]; ll sum[maxn]; const ll mod = 1000000007; ll dp[1010][1010]; int main() { int n, m; while(~scanf("%d %d", &n, &m)) { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) scanf("%I64d", &a[i]); for(int i = 1; i <= m; i++) scanf("%I64d", &b[i]); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = (((dp[i - 1][j] + dp[i][j - 1]) % mod - dp[i - 1][j - 1] + mod) + (a[i] == b[j] ? dp[i - 1][j - 1] + 1 : 0)) % mod; } } printf("%I64d\n", dp[n][m] % mod); } }
原文:http://www.cnblogs.com/lonewanderer/p/5730065.html