1401: Sherlock and Moriarty II
时间限制: 1 Sec 内存限制: 128 MB提交: 89 解决: 31
[提交][状态][讨论版]
题目描述
Sherlock Holmes is an excellent detective and Moriarty is the big villain. One day Moriarty kidnaps Sherlock's
boyfriend ---- Jhon Watson. Of course,Sherlock goes to save him. As sherlock has found the password in the previous
problem.When he finds Jhon, there is a time bomb. Sherlock has to defuse the bomb.
The bomb has a special coded lock,the lock has two sequence A and B, Sherlock has to find a new Sequence C , C is
both the subsequence of A and B, and for each i<j C[i]<C[j]. The length of C should be as long as possible.The length
of sequence C is the password.
输入
There are several cases.
For each case,the first line is N and M (1<=n,m<=100)
And the is sequence A and B , length(A)=N length(B)=M （0<= A[i],B[i]<=50）
输出
The length of sequence C.
样例输入
5 5
1 2 0 4 5
1 0 4 5 2
样例输出
3
这是最复杂
#include<stdio.h> #include<string.h> struct node{ int max, len; }; int a[101]; int b[101]; node c[101][101]; int asize, bsize; int main(){ //freopen("in.txt", "r", stdin); while (~scanf("%d%d", &asize, &bsize)){ int i, j,m,n; for (i = 0; i < asize; i++) scanf("%d", &a[i]); for (i = 0; i < bsize; i++) scanf("%d", &b[i]); memset(c, 0, sizeof(c)); for (i = 0; i < asize;i++) for (j = 0; j < bsize; j++) { if (a[i] != b[j])continue; c[i][j].len = 1; c[i][j].max = a[i]; for (m = 0; m < i;m++) for (n = 0; n < j; n++) if (c[m][n].max<a[i] && 1 + c[m][n].len>c[i][j].len) c[i][j].len = 1 + c[m][n].len; } m = 0; for (i = 0; i < asize;i++) for (j = 0; j < bsize; j++){ if (c[i][j].len>m)m = c[i][j].len; } printf("%d ", m); } return 0; }