HDU 5791 Two DP

时间：2022-05-20 07:16:07

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
2
3

题意：

　　给你两个数组

　　问你有多少对公共子序列

题解：

　　设定dp[i][j] 表示以i结尾 j结尾的子序列的 答案数

　　n^2的转移

　　 假设当前为 a[i] == b[j] , 那么它可以继承的 就是 所有 的 i,j组合 +1

　　 a[i] != b[j] 则 当前dp[i][j] = 0 咯

　　第一中继承 只需要利用前缀 优化就行

　　最后统计答案的话 就是sum[n][m]咯

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N = 1e3+, M = 2e2+, inf = 2e9, mod = 1e9+;

typedef long long ll;

ll dp[N][N],sum[N][N],ans = ;

int a[N],b[N],n,m;

int main()

{

    while (scanf("%d%d", &n, &m)!=EOF) {

        for (int i=;i<=n;i++) scanf("%d", &a[i]);

        for (int i=;i<=m;i++) scanf("%d", &b[i]);

        memset(dp,,sizeof(dp));

        memset(sum,,sizeof(sum));

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

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

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

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

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

            } else sum[i][j]=(-sum[i-][j-]%mod+sum[i-][j]%mod+sum[i][j-])%mod;

        ans=;

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

            for (int j=;j<=m;j++) ans=(ans+dp[i][j])%mod;

        printf("%I64d\n", (ans+mod)%mod);

    }

    return ;

}

　　

相关文章