HDU 1423
链接
考虑到有性质:
只要是两序列公共的子序列,只要保证一个序列是上升的即可。
状态的设置十分关键。
这里设的十分巧妙。
\(f[i][j]\)表示A序列匹配到了\(i\),B序列匹配到了\(j\)并且最长公共上升子序列以j结尾.
转移:
当\(a_i == a_j\)时
\[f[i][j] = max(f[i - 1][k] | k < j,b_k < b_j) + 1\]
我们可以从小到大枚举 j, 动态维护 max{dp(i − 1,k) | B k < A i } 直
接转移即可.
可以压掉一维.
话说,ACM的格式这么鬼畜么,WA了好几发。
/*header*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#define gc getchar()
#define pc putchar
#define mk make_pair
#define fi first
#define se second
using std::min;
using std::max;
using std::swap;
inline int gi() {
int x = 0,f = 1;char c = gc;
while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}return x * f;
}
const int maxN = 500 + 7;
int a[maxN] , b[maxN];
int f[maxN];
int main() {
int T = gi();
while(T --) {
int n , m;
memset(f , 0, sizeof(f));
n = gi();for(int i = 1;i <= n;++ i) a[i] = gi();
m = gi();for(int i = 1;i <= m;++ i) b[i] = gi();
int ans = 0;
for(int i = 1;i <= n;++ i) {
int k = 0;
for(int j = 1;j <= m;++ j) {
if(a[i] == b[j]) f[j] = f[k] + 1;
if(b[j] < a[i] && f[j] > f[k]) k = j;
ans = max(ans , f[j]);
}
}
printf("%d\n",ans);
if(T) puts("");
}
return 0;
}