HDU 5791 Two (DP)

时间:2022-06-09 07:46:37

Two

题目链接:

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

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

Source

2016 Multi-University Training Contest 5

##题意:

求A和B中有多少对子集完全相同.


##题解:

动态规划.
dp[i][j]:分别处理到i\j时ai==bj且用上ai bj后的对数. (ai!=bj时dp=0)
前缀和优化:
sum[i][j]:分别处理到i\j时满足条件的子集对数. (不一定用上ai bj)

状态转移:
dp[i][j] = sum[i-1][j-1] + 1;
用上ai bj后的对数为i\j之前的任意子集对再加上(ai, bj)这对子集.
sum[i][j] = dp[i][j] + (sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]);
前缀和由当前满足条件的对数 + 之前满足条件的对数而来(去重).


##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 1100
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

int n, m;

int a[maxn];

int b[maxn];

LL dp[maxn][maxn];

LL sum[maxn][maxn];

int main(int argc, char const *argv[])

{

//IN;

//int t; cin >> t;
while(scanf("%d %d", &n,&m) != EOF)
{
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=m; i++) scanf("%d", &b[i]); memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum)); for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i] == b[j]) {
dp[i][j] = (sum[i-1][j-1] + 1LL) % mod;
}
sum[i][j] = (dp[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mod) % mod;
}
} LL ans = sum[n][m]; /*
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i] == b[j])
ans = (ans + dp[i][j]) % mod;
}
}
*/ printf("%I64d\n", ans);
} return 0;

}