c语言sscanf函数的用法是什么
248
2022-08-27
HDU 5791 Two (DP)
Two
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 540 Accepted Submission(s): 242
Problem 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
Author
ZSTU
Source
2016 Multi-University Training Contest 5
Recommend
wange2014 | We have carefully selected several similar problems for you: 5792 5790 5789 5788 5787
题意:给你a,b两个数组,问你有多少个公共子序列。
题解:DP。
设dp[ i ][ j ]表示a中前i个和b中前j个并且a[i]==b[j]匹配的子序列个数。
那么dp[ i ][ j ] = dp[ i-1 ][ j ]+dp[ i ][ j-1 ]-dp[ i-1 ][ j-1 ]。
当a[ i ]=b[ j ]时,dp[ i ][ j ]+=dp[ i-1 ][ j-1 ]+1
注意dp转移时要特殊处理一下。这题就可以了。
AC代码:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~