zoj2432 hdoj1423 最長公共上升子序列（LCIS），zoj2432hdoj1423
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}
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
![]()
#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
![]()
#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
