轻敌了啊...题目一共只有几句话但我却忽略了一个重大信息...
总之我显示写出了时空复杂度都是n^2级别的朴素递推算法，这没什么，基本功而已，然后50分
我试了试滚动数组，把空间复杂度降到了n级别，但没什么用，解决了MLE但仍然TLE。
后来我想到记搜应该能算的更快，毕竟有些用不到的点用搜索就不用算了，但是空间不允许开n^2，所以我先是试着只抛弃那些没用到的点，即搞了一个pos->int的map，pos是一个自定义数据结构含有两个int表示数组下标。期间遇到编译错误， 然后就学到了一个知识点那就是unordered_map不需要比较运算符但是map需要比较运算符，也就是说如果自定义数据结构那你就必须给出operater<，更重要的是还必须声明这是一个const成员函数，即写成bool operator<(const pos & b)const的形式，后面这个const表示这个成员函数绝对不改数据，不加它就报错....总之解决问题后成功用上了这个做法，然后好像是60分了
再然后我想不如利用更多的空余空间，谁说记搜和滚动数组不能一起用，于是我成功了，分别基于动态数组和map各设计了一套空间复杂度极低的记忆化搜索算法，但我TMD写完之后才意识到不是记搜用不了滚动数组，而是记搜用滚动数组将不得不负责清理数组而不能无脑覆盖，因为记搜的调表顺序不同，可问题在于清理数组是一个O（n）级别的操作这就导致滚动数组式的dp几乎铁定耗时比递推滚动数组要满，空间复杂度还只能勉强一样，那显然还不如最开始的写法呢...果然，只有十分二十分....越写越回旋
写的我都饿了，就去看了看题解，才发现我忽略了一个条件那就是两个数列都是1~n的全排列！这道最长公共子序列可以转换成最长上升子序列...
啊啊啊啊啊啊所以最后我没做出来这道题在于我一开始就想偏了，普通的最长公共子序列压根就不存在！不存在！O（n^2）的算法！！！我一直在寻找一个不存在的东西当然一无所获...
当然也不算是一无所获，毕竟我获得了map、unordered_map相关的更深层的理解和更高的运用熟练度，还意识到了记搜能搞滚动数组但是不应该搞滚动数组...以及尝试用记搜代替递推的方式似乎几乎不可能解决耗时问题...
总之这道最长公共子序列不是一道普通的最长公共子序列题，是一道变了形的最长上升子序列题，那么答案很显然了。
朴素滚动数组DP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int n,a[100000+5],b[100000+5],dp[100000+5],new_dp[100000+5];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i]==b[j]) new_dp[j]=1+dp[j-1];
else new_dp[j]=max(dp[j],new_dp[j-1]);
}
for(int j=n;j>=1;j--)dp[j]=new_dp[j];
}
printf("%d",dp[n]);
return 0;
}
记搜+map-Code
#include <iostream>
#include <map>
using namespace std;
int n,a[100000+5],b[100000+5];
struct pos
{
int x;int y;
pos(){}
pos(int X,int Y){x=X;y=Y;}
bool operator<(const pos & b)const
{
if((this->x)!=(b.x))return (this->x)<(b.x);
else return (this->y)<(b.y);
}
};
map<pos,int> dp;
int dfs(int i,int j)
{
if(i==0||j==0)return 0;
pos && POS=pos(i,j);
if(dp.count(POS)==1)return dp[POS];
if(a[i]==b[j]) return dp[POS]=1+dfs(i-1,j-1);
else return dp[POS]=max(dfs(i-1,j),dfs(i,j-1));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
printf("%d",dfs(n,n));
return 0;
}
记搜+滚动数组Code1
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
using namespace std;
int n,a[100000+5],b[100000+5];
unordered_map<int,int>dp;
int dfs(int i,int j)
{
if(i==0||j==0)return 0;
if(dp.count(j)!=0)return dp[j];
if(a[i]==b[j])
{
dp.clear();
return 1+dfs(i-1,j-1);
}
else
{
int ans1=dfs(i,j-1);
dp.clear();
int ans2=dfs(i-1,j);
return max(ans1,ans2);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
printf("%d",dfs(n,n));
return 0;
}
记搜+滚动数组Code2
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int n,a[100000+5],b[100000+5];
int * dp;
int dfs(int i,int j)
{
if(i==0||j==0)return 0;
if(dp[j]!=-1)return dp[j];
if(a[i]==b[j])
{
delete[] dp;
dp=new int [j];
for(int k=0;k<j;k++)dp[k]=-1;
return 1+dfs(i-1,j-1);
}
else
{
int ans1=dfs(i,j-1);
delete []dp;
dp=new int [j+1];
for(int k=0;k<=j;k++)dp[k]=-1;
int ans2=dfs(i-1,j);
return max(ans1,ans2);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
dp=new int [n+1];
for(int k=0;k<=n;k++)dp[k]=-1;
printf("%d",dfs(n,n));
return 0;
}