Polariserist @ 2020-08-11 21:36:55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5005;
int a[N],b[N];
int f[N][N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[i][j]=max(f[i][j-1],f[i-1][j]);
if(a[i-1]==b[j-1])
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][n]<<"\n";
return 0;
}就20分。。。
by 青鱼Official @ 2020-08-11 21:38:02
建议学习正解。
by LX_Yao @ 2020-08-11 21:40:06
@Avengers_Endgame 不二分就只有被卡。
by Polariserist @ 2020-08-11 21:49:42
二分。。。？
by zero4338 @ 2020-08-12 16:00:15
@Avengers_Endgame 有一个不二分的玄学做法
by zero4338 @ 2020-08-12 16:00:35
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n;
int ans;
int b[maxn],trans[maxn];
struct number
{
int num,val;
};
number a[maxn];
int f[maxn];
int bit[maxn];
int lowbit(int x)
{
return x&-x;
}
int query(int p)
{
int ret=0;
for(;p;p-=lowbit(p))ret=max(ret,bit[p]);
return ret;
}
void add(int p,int x)
{
for(;p<=n;p+=lowbit(p))bit[p]=max(bit[p],x);
}
bool comp(number x,number y)
{
return x.val<y.val;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].val);a[i].num=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++)trans[b[i]]=i;
for(int i=1;i<=n;i++)a[i].val=trans[a[i].val];
sort(a+1,a+n+1,comp);
for(int i=1;i<=n;i++)
{
add(a[i].num,query(a[i].num-1)+1);
}
ans=query(n);
printf("%d",ans);
return 0;
}by Polariserist @ 2020-08-12 18:33:31
@zero4338 啥东西
by 旭日临窗 @ 2020-08-13 09:53:09
@Avengers_Endgame 用dp会超时的，dp的时间复杂度是O(n^2)， n可以达到10^5，必然会超时，你可以改一种方法，不用dp去做这道题
by 旭日临窗 @ 2020-08-13 09:54:27
@Avengers_Endgame 这道题如果数据小一点的话，你这个方法是没问题的
by Polariserist @ 2020-08-13 18:27:49
谢谢大佬