Prince and Princess_dp
程序员文章站
2023-12-26 12:41:03
...
https://cn.vjudge.net/problem/UVA-10635#
相同元素出现的位置
//#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=250*250+10;
int p[N],q[N],dp[N];
int main(){
// freopen("in.txt","r",stdin);
int t;
cin>>t;
int z=1;
while(t--){
int n,p1,q1;
cin>>n>>p1>>q1;
for(int i=0;i<=p1;i++){
int t;
scanf("%d",&t);
p[t]=i;
}
for(int i=0;i<=q1;i++){
int t;
scanf("%d",&t);
q[i]=p[t];
}
int ans=1;
dp[1]=q[0];
for(int i=1;i<=q1;i++){
int k=lower_bound(dp+1,dp+1+ans,q[i])-dp;
dp[k]=q[i];
ans=max(ans,k);
}
printf("Case %d: %d\n",z++,ans);
}
// fclose(stdin);
}
//#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=250*250+10;
int p[N],q[N],dp[N];
int main(){
freopen("in.txt","r",stdin);
int t;
cin>>t;
int z=1;
while(t--){
int n,p1,q1;
cin>>n>>p1>>q1;
for(int i=0;i<=p1;i++){
int t;
scanf("%d",&t);
p[t]=i;
}
for(int i=0;i<=q1;i++){
int t;
scanf("%d",&t);
q[i]=p[t];
}
int ans=1;
for(int i=0;i<=10;i++)
printf("%d ",p[i]);
puts("");
for(int i=0;i<=10;i++)
printf("%d ",q[i]);
puts("");
dp[1]=q[0];
for(int i=1;i<=q1;i++){
int k=lower_bound(dp+1,dp+1+ans,q[i])-dp;
dp[k]=q[i];
ans=max(ans,k);
cout<<"i:"<<i<<endl;
for(int j=0;j<10;j++)
cout<<dp[j]<<" ";
cout<<endl;
}
printf("Case %d: %d\n",z++,ans);
}
fclose(stdin);
}