病毒（湖南第八届大学生计算机程序设计竞赛）

病毒（湖南省第八届大学生计算机程序设计竞赛）

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=30746#problem/J
病毒Time Limit:3000MS     Memory Limit:131072KB     64bit IO Format:%lld & %lluSubmit Status Practice CSU 1120

Description

Input

Output

Sample Input

1 9 1 4 2 6 3 8 5 9 1 6 2 7 6 3 5 1

Sample Output

3
动规题。如下图，打表出来，第一行是a，第一列是b，然后进行对比，如果找到相同，则在返回来找前面是否有比当前数值小的。
6找到的时候发现前面有个2满足条件，则数量加一。5的时候前面有2和3都满足条件，所以总数为3.AC代码：

// Rujia Liu#include<cstdio>#include<algorithm>#include<vector>using namespace std;const int maxn = 1000 + 10;int n, m, A[maxn], B[maxn], last[maxn], d[maxn][maxn], f[maxn][maxn];int main() {  int T;  scanf("%d", &T);  while(T--) {    scanf("%d", &n);    for(int i = 0; i < n; i++) scanf("%d", &A[i]);    scanf("%d", &m);    for(int i = 0; i < m; i++) scanf("%d", &B[i]);    for(int j = 0; j < m; j++) {      last[j] = -1;      for(int k = 0; k < j; k++) if(B[k] == B[j]) last[j] = max(last[j], k);    }    int ans = 0;    for(int i = 0; i < n; i++)      for(int j = 0; j < m; j++) {        d[i][j] = 0;        if(A[i] == B[j]) {          d[i][j] = 1;          if(last[j] >= 0) d[i][j] = max(1, d[i][last[j]]);          if(i > 0)            for(int k = last[j]+1; k < j; k++)              if(B[k] < B[j]) d[i][j] = max(d[i][j], f[i-1][k] + 1);        }        f[i][j] = d[i][j];        if(i > 0) f[i][j] = max(f[i-1][j], f[i][j]);        ans = max(ans, d[i][j]);      }    printf("%d\n", ans);  }  return 0;}