题目传送门：https://uva.onlinejudge.org/index.php&problem=1576
中文题面：《算法竞赛·入门经典·训练指南》P66
这题真的是好妙啊！
首先O(n^4)的DP大家都会吧？
来说一说O(n*log(n))的做法：
将A串重新编号为1、2、3、4、5····
然后将编码的对应关系应用到B上面去
这样的话，就变成了求B的LIS了
于是搞一个BIT什么的就可以辣！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 250+9;
const int M = N * N;
int n,m,q,p,A[M],B[M],trans[M],vout[M];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&-(x))
int MX[M];
inline void modify(int pos, int val) {
for (int i=pos;i<=m;i+=lowbit(i))
MX[i] = max(MX[i], val);
}
inline int query(int pos) {
int ret = 0;
for (int i=pos;i;i-=lowbit(i))
ret = max(ret, MX[i]);
return ret;
}
};
int main(){
for (int k=1,T=read();k<=T;k++) {
n = read(); m = n * n + 1;
p = read() + 1; q = read() + 1;
for (int i=1;i<=p;i++) A[i] = read();
for (int i=1;i<=q;i++) B[i] = read();
memset(trans,0,sizeof(trans));
memset(vout,0,sizeof(vout));
memset(BIT::MX,0,sizeof(BIT::MX));
for (int i=1;i<=p;i++) trans[A[i]] = i;
for (int i=1;i<=q;i++) B[i] = trans[B[i]];
for (int i=1;i<=q;i++) if (B[i]) {
vout[i] = BIT::query(B[i]) + 1;
BIT::modify(B[i],vout[i]);
}
int ret = 0;
for (int i=1;i<=q;i++)
ret = max(ret, vout[i]);
printf("Case %d: %d\n",k,ret);
}
return 0;
}
We are a group of volunteers and starting a new scheme in our community.
Your website offered us with valuable info to
work on. You’ve done a formidable process and our whole community will
probably be thankful to you.
Greetings from Colorado! I’m bored at work so I decided to browse your blog on my iphone during lunch break.
I love the knowledge you provide here and can’t wait to take a look when I get home.
I’m shocked at how quick your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyways,
very good blog!
I blog quite often and I genuinely appreciate your
content. This great article has really peaked my interest.
I will take a note of your website and keep checking for
new details about once per week. I subscribed to your Feed as well.
Someone essentially help to make critically posts I might state.
That is the first time I frequented your web page and thus far?
I surprised with the analysis you made to make this actual publish
extraordinary. Magnificent task!
Wow, this post is fastidious, my sister is analyzing these kinds of things, so I am
going to let know her.
Have you ever thought about including a little bit more than just your articles?
I mean, what you say is important and everything. But just imagine if you added some great photos or video clips to give your posts more, “pop”!
Your content is excellent but with pics and clips, this website could undeniably be one of the greatest in its niche.
Awesome blog!
This design is wicked! You most certainly know how to keep a reader entertained.
Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Fantastic job. I really enjoyed what you
had to say, and more than that, how you presented it.
Too cool!
Way cool! Some very valid points! I appreciate you penning this write-up and the rest of the site
is very good.
Somebody essentially lend a hand to make significantly articles I’d state.
This is the very first time I frequented your website page and up
to now? I amazed with the analysis you made to create
this particular publish incredible. Wonderful activity!
I got this site from my buddy who shared with me about this site
and at the moment this time I am visiting this web page and reading very
informative content here.
Does your site have a contact page? I’m having problems locating it but, I’d like to shoot you an email.
I’ve got some recommendations for your blog you might be interested in hearing.
Either way, great site and I look forward to seeing it improve
over time.
I blog frequently and I genuinely appreciate your content.
This great article has really peaked my interest.
I will take a note of your blog and keep checking for new details about once per week.
I opted in for your Feed as well.
You are my intake, I possess few blogs and often run out from to brand : (.
Do you have a spam issue on this blog; I also am a blogger, and I was wanting to know your situation; we have developed some nice methods and we are looking to trade strategies with other folks, be sure to shoot me an e-mail if interested.
This is my first time go to see at here and i am truly impressed to read
all at single place.
I do agree with all the ideas you have offered to your
post. They’re really convincing and will definitely work.
Nonetheless, the posts are too short for novices. May just you
please prolong them a bit from subsequent time? Thank you for the
post.
It’s awesome to visit this web site and reading the views of all mates regarding this post,
while I am also zealous of getting know-how.
We stumbled over here different web page and thought
I might as well check things out. I like what I see so now i am following you.
Look forward to finding out about your web page yet again.
Hmm is anyone else having problems with the pictures on this
blog loading? I’m trying to figure out if its a problem on my end or
if it’s the blog. Any feed-back would be greatly appreciated.
Pretty nice post. I just stumbled upon your weblog and wished to say that
I have really enjoyed browsing your blog posts. In any case I’ll be subscribing to your rss feed and I hope
you write again soon!
I like the helpful info you provide in your articles.
I’ll bookmark your blog and check again here regularly.
I am quite certain I will learn many new stuff right here!
Good luck for the next!
Attractive section of content. I just stumbled upon your blog and in accession capital to assert that I acquire actually enjoyed account your blog posts. Anyway I’ll be subscribing to your augment and even I achievement you access consistently fast.