相同的数列

时间: 1ms        内存:128M

描述:

    Zp幸运的得到了两个序列A和B,现在Zp想知道数列A和数列B的非空子数列有多少对是相同的。例如,{1,2}和{1,2}是相同的,而{1,2,4}和{1,4,2}是不同的。子序列可以是不连续的,例如,{1,1,2}有7个非空子序列{1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}。最后的结果可能非常大,输出答案mod 1000000007。

输入:

输入包含多组数据。
对于每组数据:
第一行包含两个整数N,M(1≤N,M≤1000);
第二行有N个整数,表示第一个数列;
第三行有M个整数,表示第二个数列。
所有的数字的取值范围为[1,1000]。

输出:

输出对1000000007取模后的结果。

示例输入:

3 2
1 2 3
2 1
3 2
1 2 3
1 2

示例输出:

2
3

提示:

参考答案(内存最优[5656]):

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N=1e9+7;
int e[1005][1005];
int main(){
    int n,m;
    int a[1005],b[1006];
    while(cin>>n>>m){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(e,0,sizeof(e));
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<m;i++)
            scanf("%d",&b[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
        {
            if(a[i]==b[j])
                e[i+1][j+1]=(e[i][j+1]+e[i+1][j]+1)%N;
            else
                e[i+1][j+1]=(e[i+1][j]+e[i][j+1]-e[i][j]+N)%N;
        }
        cout<<e[n][m]<<endl;
    }
}

参考答案(时间最优[12]):

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int MAXN = 1e3+5;
int n,m;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int main()
{
	while (cin>>n>>m)
	{
		memset(dp,0,sizeof dp);
		for (int i=1;i<=n;i++) cin>>a[i];
		for (int i=1;i<=m;i++) cin>>b[i];
		for (int i=1;i<=n;i++) 
			for (int j=1;j<=m;j++)
			{
				if (a[i]==b[j]) dp[i][j]=(dp[i-1][j]+dp[i][j-1]+1)%mod;
				else dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%mod;
			}
		cout<<dp[n][m]<<endl;
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。