欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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);
}



Prince and Princess_dp

上一篇:

下一篇: