前言
期末考试前的最后一篇题解，希望期末考 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#include 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\n", ans); if (ans) //特判是否存在长度>0的序列 f (i, 1, l2) if (f[l1][i] == ans) {print(i); break;} //找到最优解的末尾位置并输出序列 return 0;}
优化后
#include#include 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\n", ans); if (ans) //特判是否存在长度>0的序列 f (i, 1, l2) if (f[i] == ans) {print(i); break;} //找到最优解的末尾位置并输出序列 return 0;}