A22627 @AC君 建议修改检测点!
2024-07-30 01:09:52
发布于:广东
33阅读
0回复
0点赞
A22627最长公共子序列的检测点与题意描述不符 建议修改!!!
题目的P1与P2给的是自然数1-n的排列,但是检测点1内容完全偏离题意
同时这道题给的数据是 像提交记录里dp暴力的写法复杂度是按照这样的数据时间肯定会超1s的,但是这样写法ACGO上是全AC的
但在洛谷上交会TLE
下面提供测试代码
1 DP暴力写法
#include <bits/stdc++.h>
using namespace std;
int s1[1005],s2[1005];
int n;
int dp[1005][1005];//dp[i][j]代表到当前s1的第i元素和s2的第j元素为止,其前面(包含自己)的LCS最长长度
int main(){
memset(dp,0,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++){cin>>s1[i];}
for(int i=1;i<=n;i++){cin>>s2[i];}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//状态转移方程
if(s1[i]==s2[j]){//1->当s1第i元素不等于s2第j元素时
dp[i][j]=dp[i-1][j-1]+1;//当相等时,当前的dp[i][j]等于前面的最长LCS+1(1指自己的长度)
}
else{//2->当s1第i元素不等于s2第j元素时
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
//当不相等时,考虑去掉s1第i元素/s2第j元素的情况时dp表的状况,选择其中大的
}
}
}
cout<<dp[n][n];//输出dp表的最后一项
return 0;
}
2 二分转换最长子序列写法 O(nlogn)
#include <bits/stdc++.h>
using namespace std;
int s1[100005],s2[100005];
int mapn[100005];//存储s1(基准数组)的每个元素出现的下标
set<int> dp;//用以存储LIS最长上升子序列
set<int>::iterator it;
//mapn[i]代表s1中第i元素出现的位置,即i
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){cin>>s1[i];mapn[s1[i]]=i;}//存放map
for(int i=1;i<=n;i++){cin>>s2[i];}
dp.insert(mapn[s2[1]]);//先放入第一个,从第二个开始二分查找O(nlogn)
for(int i=2;i<=n;i++){
it=dp.lower_bound(mapn[s2[i]]);
if(it!=dp.end()){//如果找到了比当前大的
dp.erase(it);
}
dp.insert(mapn[s2[i]]);
//for(it=dp.begin();it!=dp.end();it++)cout<<*it<<' ';
//cout<<endl;
}
cout<<dp.size();
//现在二分后,dp内已是s1与s2的最长公共子序列了,所以直接输出dp元素个数
return 0;
}
评测环境:
系统Win11
终端Edge浏览器
全部评论 2
好的,感谢反馈,已记录。
2024-07-30 来自 浙江
0AAAA
2024-07-30 来自 广东
0
有帮助,赞一个