http://acm.hdu.edu.cn/showproblem.php?pid=5791

Two

Problem Description

Alice gets two sequences A and B. A easy problem comes. How many pair of sequence A' and sequence B' are same. For example, {1,2} and {1,2} are same. {1,2,4} and {1,4,2} are not same. A' is a subsequence of A. B' is a subsequence of B. The subsequnce can be not continuous. For example, {1,1,2} has 7 subsequences {1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}. The answer can be very large. Output the answer mod 1000000007.

Input

The input contains multiple test cases.

For each test case, the first line cantains two integers N,M(1≤N,M≤1000). The next line contains N integers. The next line followed M integers. All integers are between 1 and 1000.

Output

For each test case, output the answer mod 1000000007.

Sample Input

3 2

1 2 3

2 1

3 2

1 2 3

1 2

Sample Output

题意：有两个串，求两两子串相同的个数有多少（可以不连续）。

思路：有点类似于LCS的DP，（+MOD）%MOD是因为有可能减出负数，因为取MOD一开始可能很大，后面变得很小。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define N 1005

 #define MOD 1000000007

 typedef long long LL;

 LL dp[N][N];

 int a[N], b[N];

 /*

 1 2 3

 2 1

 */

 int main()

 {

     int n, m;

     while(~scanf("%d%d", &n, &m)) {

         dp[][] = ;

         for(int i = ; i <= n; i++) {

             scanf("%d", a+i);

             dp[i][] = ;

         }

         for(int i = ; i <= m; i++) {

             scanf("%d", b+i);

             dp[][i] = ;

         }

 /*

 有这三部分

 dp[i-1][j-1]

 dp[i-1][j] - dp[i-1][j-1]

 dp[i][j-1] - dp[i-1][j-1]

 如果不匹配的话 dp[i][j] = dp[i-1][j] - dp[i-1][j-1] + dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j-1]

 匹配的话 dp[i][j] = 不匹配的状态 + dp[i-1][j-1] + 1

 dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] 表示当前不匹配的状态有多少种，因为dp[i-1][j]和dp[i][j]中有dp[i-1][j-1]重复，所以要减去一个

 如果当前匹配的话，就不用减去，因为要留一个来和当前的a[i]和b[j]匹配。

 */

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= m; j++) {

                 if(a[i] == b[j]) {

                     dp[i][j] = (dp[i-][j] + dp[i][j-] +  + MOD) % MOD;

                 } else {

                     dp[i][j] = (dp[i-][j] + dp[i][j-] - dp[i-][j-] + MOD) % MOD;

                 }

             }

         }

         printf("%I64d\n", dp[n][m] % MOD);

     }

     return ;

 }

巴特西

HDU 5791：Two（DP）

Two

最新文章

热门文章