模板 CF10D
参考 chennachuan_2004
/*
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=5005;
int N, M, A[MAXN], B[MAXN];
int f[MAXN][MAXN], ansj=0, lcis[MAXN][MAXN];
void LCIS();
void Input();
int main()
{
Input();
LCIS();
printf("%d
",f[N][ansj]);
for (int p=1; p<=f[N][ansj]; p++)
printf("%d ",lcis[ansj][p]);
puts("");
return 0;
}
void LCIS()
{
memset (f, 0, sizeof(f));
memset (lcis, 0, sizeof(lcis));
for (int i=1; i<=N; i++)
{
for (int j=1,k=0; j<=M; j++)
{
if (A[i] == B[j])
{
f[i][j] = f[i-1][k]+1;
for (int p=1; p<=f[i-1][k]; p++)
lcis[j][p] = lcis[k][p];
lcis[j][f[i][j]] = A[i];
}
else f[i][j] = f[i-1][j];
if (B[j]<A[i] && f[i][j]>f[i][k])
k = j;
}
}
for (int i=1; i<=M; i++)
if (f[N][i] > f[N][ansj])
ansj = i;
return;
}
void Input()
{
scanf("%d",&N);
for(int i=1; i<=N; i++)
scanf("%d",&A[i]);
scanf("%d",&M);
for(int i=1; i<=M; i++)
scanf("%d",&B[i]);
return;
}
方法1
设 lcis[j][1~f[i][j]] 储存以B[j]结尾, A[1~i] 和 B[i~j] 的LCIS.
注意, lcis[][] 两个维度的意义与 f[][] 并不相同,这里已经使用 i,j 将它们进行了区分.
每次转移时将 lcis[j][1~f[i-1][k]] 完全复制到 lcis[j][1~f[i][j]-1] 上,
再在后面的 lcis[j][f[i][j]] 的位置增加一个 B[j].
最后找到 LCIS 最长的结束位置 ansj ,将 lcis[ansj][1~f[N][ansj]] 输出
这种方法中,由于多重if语句的限制,实际运行速度很快,
甚至可以通过 N=5000 的多组极端数据.时间复杂度不好估计,大约在 O(n^3) 左右.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
#define lson x<<1
#define rson x<<1|1
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
int f = 1;x = 0;
char c = getchar();
for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x *= f;
}
template <typename xxx> inline void print(xxx x)
{
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) print(x/10);
putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 5005;
const int mod = 10007;
int a[maxn];
int b[maxn];
int dp[maxn][maxn];//以b[j]结尾的，a[1-i]与b[i-j]的LCIS
int lu[maxn][maxn];
int n,m,ansj;
inline void input(){
read(n);for(rint i = 1;i <= n; ++i) read(a[i]);
read(m);for(rint i = 1;i <= m; ++i) read(b[i]);
return ;
}
inline void LCIS(){
for(rint i = 1;i <= n; ++i) {
for(rint j = 1,k = 0;j <= m ; ++j) {
if(a[i] == b[j]) {//max{dp[i-1][k]} + 1,1 <= k < j,b[k] < b[j]
dp[i][j] = dp[i-1][k] + 1;
lu[i][j] = k;//a中前i个与b中前j个并以b[j]结尾的LCIS的倒数第二项
}
else {//a[i]^b[j],由定义有a[i]与dp[i][j]无关，dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i-1][j];
lu[i][j] = j;// lu[i][j] == j ,则说明这里是没有增加LCIS长度的转移,
}
if(b[j] < a[i] && dp[i][j] > dp[i][k]) k = j;//由于i在外层，导致内层的一遍循环中a[i]不变，转移方程要求是在a[i] == b[j]时
}//找到dp[i-1]中使结尾b[k]小于b[j]的，k<j的LCIS,则可以随着j循环，更新k的值
}
for(rint i = 1;i <= m; ++i)
if(dp[n][i] > dp[n][ansj]) ansj = i;//找最长
return ;
}
inline void output(int i,int j) {
if(i == 0) return ;
output(i - 1,lu[i][j]);
if(lu[i][j] ^ j) print(b[j]),putchar(' ');// 没有增加LCIS长度的转移,应该沿着f[i][j]转移时的路径继续递归,但不输出.直到 lu[i][j] != j 就输出b[j].
return ;
}
int main()
{
input();LCIS();
print(dp[n][ansj]);putchar('
');
if(dp[n][ansj]) {
output(n,ansj);
putchar('
');
}
return 0;
}
/*
设 path[i][j] 是 f[i][j] 转移时的路径.这样就将 path[i][j] 与 A[1~i]和B[1~j] 联系起来.
每次随着 f[i][j] 的转移记录 path[i][j].
k (A[i]==B[j])
path[i][j] =
j (A[i]!=B[j])
输出的递归函数Output应有两个参数(i,j),表示当前在数组A中位置是i,在数组B中位置是j.
我们沿着f[i][j]转移时的路径递归,也就是Output(i-1,path[i][j]).
若 path[i][j] == j ,则说明这里是没有增加LCIS长度的转移,
应该沿着f[i][j]转移时的路径继续递归,但不输出.直到 path[i][j] != j 就输出B[j].
这种方法的时间复杂度为O(n^3).
.................
注意到在 max{ f[i-1][k] | 1<=k<j ,B[k]<B[j] }(B[j]==A[i]) 中有1<=k<j,
也就是决策集合{k}实际上可以在j的循环中用储存最优值的方式维护一下.
当每次j++,也就是从 j-1 增加到 j 时,决策集合中会新增一个元素 k (k==j-1),
该决策合法的条件是B[k]<B[j],B[j]==A[i]
虽然随着j的增加,B[j]会变化,也许会使{k}中的一些元素退出决策集合.
但是,只有B[j]==A[i]时决策才需要用到这个决策集合{k}.
因为枚举j时A[i]不变,所以,我们保持原有的元素不变,
当B[j-1]<A[i]时,用新的决策k(k==j-1)来更新原决策集合中的最优决策.
即 if (B[j]<A[i] && f[i-1][j]>f[i-1][k]) k=j;
这样就可以不用再j的循环中再写k的循环寻找最优决策了
优化后两种方法的时间复杂度都降了一维,时间复杂度为O(n^2).
*/