转载

zoj2432 hdoj1423 最长公共上升子序列(LCIS)

zoj2431  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2432

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

题意:

一看题目题意就很明显了, 两个数组a,b,求出两个数组公共的最长的上升子序列(可以不是连续的子序列)。

分析:

如果做过 [ 最长公共子序列 ]( http://blog.csdn.net/wangdan11111/article/details/41321277 )应该更容易明白点。

定义状态d [ i ] [ j ]表示以a数组的前i个元素,b数组的前j个元素并且以b[j]为结尾的LCIS的长度。

首先:a [ i ] != b[j]时, d[i]

举个例子

a={1, 4, 2, 5, -12}   b ={5, -12, 1, 2, 4, 5}

5    -12   1   2   4   5  
1   0 0 1 0 0 0
4    0 0 1 0 2 0
2 0 0 1 2 2 0
5 1 0 1 2 2 3
-12 1 1 1 2 2 3

if(a[i] == b[j])

d[i][j] = mx + 1;

else  if(a[i] > b[j] && mx < d[i-1][j]) 

mx = d[i-1][j];

        //只有当a[i] > b[j]时,才更新mx, 保证了所求序列是上升的。

仔细看表格会发现: 若d[i][j] > 0 的话,那么在数组a前i个元素中一定存在a[k]( 1 <= k <= i)等于b[j]. 否则说明前i个a元素中没有与b[j]相同的元素。

zoj2432

zoj2432  hdoj1423  最长公共上升子序列(LCIS)
#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<math.h> using namespace std; const int N = 505; int n1, n2, t, mx, sum; int a[N], b[N], d[N][N], pi[N][N], pj[N][N]; void  dp() {  for(int i = 1; i <= n1; i++)  {   int mx = 0, x = 0, y = 0;   for(int j = 1; j <= n2; j++)   {    d[i][j] = d[i-1][j];    pi[i][j] = i-1;    pj[i][j] = j;    if(a[i] > b[j] && mx < d[i-1][j])    {     mx = d[i-1][j];     x = i-1; y = j;    }    else if(a[i] == b[j])    {     d[i][j] = mx + 1;     pi[i][j] = x;     pj[i][j] = y;    }   }  } } void ac(int x, int y) {  if(d[x][y] == 0)   return;  int fx = pi[x][y];  int fy = pj[x][y];  ac(fx, fy);  if(d[x][y] != d[fx][fy] && y != 0)  {   printf("%d", b[y]);   sum++;   if(sum < mx) printf(" ");   else    printf("/n");  } } int main() {  cin >> t;  while(t--)  {   scanf("%d", &n1);   for(int i = 1; i <= n1; i++) scanf("%d", &a[i]);   scanf("%d", &n2);   for(int i = 1; i <= n2; i++) scanf("%d", &b[i]);   memset(d, 0, sizeof(d));   memset(pi, -1, sizeof(pi));   memset(pj, -1, sizeof(pj));   dp();   mx = 0;   int flag = 0;   for(int i = 1; i <= n2; i++)   {    if(d[n1][i] > mx)    {     mx = d[n1][i];     flag = i;    }   }   printf("%d/n", mx);   for(int i = 1; i <= n1; i++)   {    for(int j = 1; j  <= n2; j++)     printf("%d ", d[i][j]);    printf("/n");   }   sum = 0;   if(mx > 0)    ac(n1, flag);   if(t)    printf("/n");  }  return 0; } 
View Code

hdoj1423

zoj2432  hdoj1423  最长公共上升子序列(LCIS)
#include<iostream> #include<cstdio> #include<string.h> #include<cstring> #include<math.h> using namespace std; int n1, n2, t, k; int a[505], b[505], d[505][505]; int dp() {  int mx;  for(int i = 1; i <= n1; i++)  {   mx = 0;   for(int j = 1; j <= n2; j++)   {    d[i][j] = d[i-1][j];    if(a[i] > b[j] && mx < d[i-1][j]) mx = d[i-1][j];    else if(a[i] == b[j])     d[i][j] = mx + 1;   }  }  mx = 0;  for(int i = 1; i <= n2; i++)  {   if(d[n1][i] > mx)     mx = d[n1][i];  }  return mx; } int main() {  cin >> t;  while(t--)  {   scanf("%d", &n1);   for(int i = 1; i <= n1; i++) scanf("%d", &a[i]);   scanf("%d", &n2);   for(int i = 1; i <= n2; i++) scanf("%d", &b[i]);   memset(d, 0, sizeof(d));   int ans = dp();   printf("%d/n", ans);   if(t) printf("/n");  }  return 0; } 
View Code
正文到此结束
Loading...