前言
期末考试前的最后一篇题解，希望期末考 rp++
奇怪，为什么在CF上能过的代码到POJ上就 听取WA声一片 （不管了）
题目思路
LCIS模版O(n²)+方案记录（递归输出）
LCIS
基础方法
简单易想的方法：直接将LCS和LIS简单相加，复杂度O(n³)
for (int i = 1; i <= l1; i++)
for (int j = 1; j <= l2; j++)
if (a[i] == b[j]) {
for (int k = 0; k < j; k++)
if (b[k] < a[i])
f[i][j] = max (f[i][j], f[i-1][k] + 1);
}
else f[i][j] = f[i-1][j];
时间优化dp
不难看出，状态转移的时候 f 数组的第一维都是由 i-1 转移过来的， 所以不必枚举每一个 k，可以用一个数把之前的最佳方案记录下来
当 i，j 满足a[i] > b[j]时，f[i-1][j]可以去更新最优方案 （因为b[j] < a[i] 时，可以构成上升序列）
#define f(i,a,b) for (int i = a; i <= b; i++)
f (i, 1, l1){
int tmp(0); //tmp记录最优解的值
f (j, 1, l2){
f[i][j] = f[i-1][j];
if (a[i] > b[j]) tmp = max (tmp, f[i-1][j]); //如果满足条件，更新最优方案
if (a[i] == b[j]) f[i][j] = tmp + 1; //如果两个数相等，答案为之前的最优情况+1
ans = max (ans, f[i][j]);
}
}
空间优化dp
因为状态转移的时候 f 数组的第一维都是由 i-1 转移过来的，所以不但在时间上可以记录最优策略来优化，空间上也可以省去第一维。
在代码实现时直接将数组第一维删去即可
#define f(i,a,b) for (int i = a; i <= b; i++)
f (i, 1, l1){
int tmp(0); //tmp记录最优解的值
f (j, 1, l2){
if (a[i] > b[j] ) tmp = f[j]; //如果满足条件，更新最优方案
if (a[i] == b[j]) f[j] = tmp + 1;
//如果两个数相等，答案为之前的最优情况+1
ans = max (ans, f[j]);
}
}
路径记录
基础方法
用一个数组 w[i][j] 来表示 f[i][j] 以 b[j] 为结尾的方案的序列的上一个数的位置。
例如样例中，样例输出 3 5 6 中，以 6 为结尾的方案的 w 数组中存的就是数字 5 的位置
#define f(i,a,b) for (int i = a; i <= b; i++)
f (i, 1, l1){
int tmp(0), k(0); //tmp记录最优解的值，k记录位置
f (j, 1, l2){
f[i][j] = f[i-1][j], w[i][j] = w[i-1][j];
if (a[i] > b[j] and f[i-1][j] > tmp)
tmp = f[i-1][j], k = j; //如果满足条件，更新最优方案
if (a[i] == b[j]) f[i][j] = tmp + 1, w[i][j] = k;
//如果两个数相等，答案为之前的最优情况+1，w 改为记录的最优方案的上一个位置
ans = max (ans, f[i][j]);
}
}
空间优化
和上面求解LCIS的最长长度的空间优化一样，w 数组的第一维在状态转移的时候，i 都是由 i-1 转移过来的，因此也可以去掉一维
#define f(i,a,b) for (int i = a; i <= b; i++)
f (i, 1, l1){
int tmp(0), k(0); //tmp记录最优解的值，k记录位置
f (j, 1, l2){
if (a[i] > b[j] and f[j] > tmp)
tmp = f[j], k = j; //如果满足条件，更新最优方案
if (a[i] == b[j]) f[j] = tmp + 1, w[j] = k;
//如果两个数相等，答案为之前的最优情况+1，w 改为记录的最优方案的上一个位置
ans = max (ans, f[j]);
}
}
方案输出
输出时先枚举每一个以 b[j] 结尾的答案与最优解对比，从而找出最优解的最后一个数（注意：要特判答案是否存在长度>0的序列，若没有不用输出，我为此WA了两次）
if (ans) //特判是否存在长度>0的序列
f (i, 1, l2)
if (f[l1][i] == ans) {print(i); break;} //找到最优解的末尾位置并输出序列
找到位置后递归输出
void print (int p) {
if (w[l1][p]) print(w[l1][p]); //如果之前还有数，先输出之前的数
printf ("%d ", b[p]);
}
优化效果
可以看出，优化后空间极其节省（虽然两种都能过）
至于时间上的差异emm······ 连续交两次同样代码跑出来的时间都差好多
完整代码
未优化
#include <cstdio>
#include <iostream>
using namespace std;
#define f(i,a,b) for (register int i = a; i <= b; i++)
int l1, l2, a[538], b[538], f[538][538], w[538][538], ans;
void print (int p) {
if (w[l1][p]) print(w[l1][p]); //如果之前还有数，先输出之前的数
printf ("%d ", b[p]);
}
int main() {
scanf ("%d", &l1);
f (i, 1, l1) scanf ("%d", a + i);
scanf ("%d", &l2);
f (i, 1, l2) scanf ("%d", b + i);
f (i, 1, l1){
int tmp(0), k(0); //tmp记录最优解的值，k记录位置
f (j, 1, l2){
f[i][j] = f[i-1][j], w[i][j] = w[i-1][j];
if (a[i] > b[j] and f[i-1][j] > tmp)
tmp = f[i-1][j], k = j; //如果满足条件，更新最优方案
if (a[i] == b[j]) f[i][j] = tmp + 1, w[i][j] = k;
//如果两个数相等，答案为之前的最优情况+1，w 改为记录的最优方案的上一个位置
ans = max (ans, f[i][j]);
}
}
printf ("%d
", ans);
if (ans) //特判是否存在长度>0的序列
f (i, 1, l2)
if (f[l1][i] == ans) {print(i); break;} //找到最优解的末尾位置并输出序列
return 0;
}
优化后
#include <cstdio>
#include <iostream>
using namespace std;
#define f(i,a,b) for (register int i = a; i <= b; i++)
int l1, l2, a[538], b[538], f[538], w[538], ans;
void print (int p) {
if (w[p]) print(w[p]); //如果之前还有数，先输出之前的数
printf ("%d ", b[p]);
}
int main() {
scanf ("%d", &l1);
f (i, 1, l1) scanf ("%d", a + i);
scanf ("%d", &l2);
f (i, 1, l2) scanf ("%d", b + i);
f (i, 1, l1){
int tmp(0), k(0); //tmp记录最优解的值，k记录位置
f (j, 1, l2){
if (a[i] > b[j] and f[j] > tmp)
tmp = f[j], k = j; //如果满足条件，更新最优方案
if (a[i] == b[j]) f[j] = tmp + 1, w[j] = k;
//如果两个数相等，答案为之前的最优情况+1，w 改为记录的最优方案的上一个位置
ans = max (ans, f[j]);
}
}
printf ("%d
", ans);
if (ans) //特判是否存在长度>0的序列
f (i, 1, l2)
if (f[i] == ans) {print(i); break;} //找到最优解的末尾位置并输出序列
return 0;
}