博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[HDOJ5791]Two(DP)
阅读量:5346 次
发布时间:2019-06-15

本文共 1247 字,大约阅读时间需要 4 分钟。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5791

题意:给两个数列,求有多少个公共子序列。

dp(i,j)表示a1~ai和b1~bj的公共子序列个数,当ai==bj的时候,dp(i,j)=dp(i-1,j)+dp(i,j-1)+1。否则dp(i,j)=dp(i-1,j)+dp(i,j-1)-dp(i-1,j-1),这是因为在加两个单独分支的时候重复加了一次dp(i-1,j-1)。但是减完以后可能会是负数,要加一个mod。

1 #include 
2 using namespace std; 3 4 typedef long long LL; 5 const LL mod = 1000000007; 6 const int maxn = 1010; 7 int n, m; 8 int a[maxn], b[maxn]; 9 LL dp[maxn][maxn];10 int main() {11 // freopen("in", "r", stdin);12 while(~scanf("%d%d",&n,&m)) {13 for(int i = 1; i <= n; i++) scanf("%d", &a[i]);14 for(int i = 1; i <= m; i++) scanf("%d", &b[i]);15 memset(dp, 0, sizeof(dp));16 for(int i = 1; i <= n; i++) {17 for(int j = 1; j <= m; j++) {18 if(a[i] == b[j]) {19 dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1;20 dp[i][j] %= mod;21 }22 else {23 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];24 dp[i][j] += mod;25 dp[i][j] %= mod;26 }27 }28 }29 cout << dp[n][m] << endl;30 }31 return 0;32 }

 

转载于:https://www.cnblogs.com/kirai/p/5987709.html

你可能感兴趣的文章
组合数学 UVa 11538 Chess Queen
查看>>
oracle job
查看>>
Redis常用命令
查看>>
[转载]电脑小绝技
查看>>
windos系统定时执行批处理文件(bat文件)
查看>>
thinkphp如何实现伪静态
查看>>
BZOJ 2243: [SDOI2011]染色( 树链剖分 )
查看>>
BZOJ 1925: [Sdoi2010]地精部落( dp )
查看>>
c++中的string常用函数用法总结!
查看>>
[DLX精确覆盖+打表] hdu 2518 Dominoes
查看>>
SuperMap iServerJava 6R扩展领域开发及压力测试---判断点在那个面内(1)
查看>>
Week03-面向对象入门
查看>>
一个控制台程序,模拟机器人对话
查看>>
web.xml 中加载顺序
查看>>
pycharm激活地址
查看>>
hdu 1207 四柱汉诺塔
查看>>
Vue 2.x + Webpack 3.x + Nodejs 多页面项目框架(上篇——纯前端多页面)
查看>>
我的PHP学习之路
查看>>
【题解】luogu p2340 奶牛会展
查看>>
对PostgreSQL的 SPI_prepare 的理解。
查看>>