甘德县公司网站建设,英语培训东莞网站建设,装修加盟好项目,网站建设项目招标标书本题由于1e5的数据#xff0c;n方的做法不再适用#xff0c;但是简单的一维并不能满足动态转移。这时#xff0c;我们就可以考虑引入最长上升子序列来处理
用样例来看
5
序列#xff1a;3 2 1 4 5序号#xff1a;1 2 3 4 5序列#xff1a;1 2 3 4 5序号#xff1a;3 2…本题由于1e5的数据n方的做法不再适用但是简单的一维并不能满足动态转移。这时我们就可以考虑引入最长上升子序列来处理
用样例来看
5
序列3 2 1 4 5序号1 2 3 4 5序列1 2 3 4 5序号3 2 1 4 5求公共子序列我们可以发现上面的序列是递增的。实际上我们只是在下面找一个最长上升子序列上面已经递增了这样考虑的原因是我们收到的一个1-n的排列每个数字只出现一次
代码如下
// Problem:
// P1439 【模板】最长公共子序列
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1439
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includealgorithm
#includevector
using namespace std;int main(){int n;cinn;vectorint a(n1);vectorint b(n1);vectorint c(n1);//vector大法好for(int i1;in;i) cina[i],c[a[i]]i;int x;for(int i1;in;i) cinx,b[i]c[x];vectorint d(n1);int cnt0;d[0]-1e9;//这里不会卡数据但是建议设置一个标兵不然后面比较会出错for(int i1;in;i){if(b[i]d[cnt]){d[cnt]b[i];}else{ //二分*upper_bound(d.begin()1,d.begin()1cnt,b[i])b[i];}}coutcntendl;return 0;
}
