1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define int long long #define lowbit(x) x&-x const int INF=0x3f3f3f3f3f3f3f3f; const int N=2e3+10; const int M=2e6+10; const int mod=1e9+7; int n,m; int a[N]; int b[N]; int dp[N][N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i][0]=1; } for(int i=1;i<=m;i++){ cin>>b[i]; dp[0][i]=1; } dp[0][0]=1; 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]-dp[i-1][j-1];//减掉两个都不用的 if(a[i]==b[j]) dp[i][j]+=dp[i-1][j-1]; dp[i][j]%=mod; dp[i][j]+=mod; dp[i][j]%=mod; } } cout<<dp[n][m]; return 0; } /* 一眼出定义 dp[i][j]表示s的i对t的j */
信息
- ID
- 1726
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 提高
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者