zoj2432 hdoj1423 最长公共上升子序列（LCIS）

深藏阁楼爱情的钟 2022-01-10 05:41 183阅读 0赞

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\]\[j\] = d\[i-1\]\[j\]; 因为 d\[i\]\[j\] 是以 b\[j\] 为结尾的LCIS，如果 d\[i\]\[j\] > 0 那么就说明 a\[1\] .... a\[i\] 中必然有一个元素 a\[k\] 等于 b\[j\]。因为 a\[k\] != a\[i\]，那么 a\[i\] 对 d\[i\]\[j\] 没有贡献，于是我们不考虑它照样能得出 d\[i\]\[j\] 的最优值。所以在 a\[i\] != b\[j\] 的情况下必然有 d\[i\]\[j\] = d\[i-1\]\[j\]。这一点参考LCS的处理方法。

当a\[i\]==b\[j\]时， 首先，这个等于起码保证了长度为1的LCIS。然后我们还需要去找一个最长的且能让b\[j\]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的d数组的第一维必然是i-1。因为i已经拿去和b\[j\]配对去了，不能用了。第二维需要枚举 b\[1\] ... b\[j-1\]了，因为你不知道这里面哪个最长且哪个小于 b\[j\]。

状态转移方程：

**a\[i\] != b\[j\]: d\[i\]\[j\]=d\[i-1\]\[j\] ；**

**a\[i\] == b\[j\]: d\[i\]\[j\]=max(d\[i-1\]\[k\]) + 1 ； （1<= k <= j-1）**

不难看到，这是一个时间复杂度为O(n^3)的DP，离平方还有一段距离。

但是，这个算法最关键的是，如果按照一个合理的递推顺序，max(d\[i-1\]\[k\])的值我们可以在之前访问 d\[i\]\[k\] 的时候通过维护更新一个max变量得到。怎么得到呢？首先递推的顺序必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了 d\[1\]\[n2\] 再去算 d\[2\]\[1\]。 如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个max变量为0，然后开始内层循环。当a\[i\]>b\[j\]的时候令max = d\[i-1\]\[j\]。如果循环到了a\[i\] == b\[j\]的时候，则令 d\[i\]\[j\] = max+1。 最后答案是 d\[n1\]\[1\] ... d\[n1\]\[n2\]的最大值。

举个例子

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
 }

hdoj1423

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
 }

转载于:https://www.cnblogs.com/wd-one/p/4470844.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/dd13b74368f445418959d0c00ff37eca.png