2016 Multi-University Training Contest 5 1011 Two DP

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

HDU5791 Two

题意 :两个数组,多少个不连续子串相等

思路:

dp[i][j] :a串i结尾,b串j结尾的不连续子串数目个数

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e3+;
const int mod=1e9+;
const int inf=0x3f3f3f3f;
ll dp[maxn][maxn],a[maxn],b[maxn];
int n,m;
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
for(int i=;i<=m;i++)scanf("%lld",&b[i]);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp[i][j]=(dp[i-][j]+dp[i][j-]-dp[i-][j-]+(a[i]==b[j]?dp[i-][j-]+:)+mod)%mod;
}
}
printf("%lld\n",dp[n][m]);
}
return ;
}
上一篇:HDU5806:NanoApe Loves Sequence Ⅱ(尺取法)


下一篇:通过Curator操作Zookeeper的简单例子代码