题目传送门：http://codeforces.com/contest/706/problem/C
数据生成器：http://paste.ubuntu.com/23048130/
不要问我这道题我做了多久QAQ
一开始是想道2-SAT
后来是写SA一直不停TLE
然后是写O(n)的暴力，仍然T到死
最后发现，是strlen的时间复杂度不对QAQ
之前，我一直以为这货是O(1)的
就是先用黑科技搞定尾地址，然后首尾地址减一减
结果查一查，发现这货是O(n)的QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 200000+9;
LL f[2][MAXN];
int pos[MAXN],n,c[MAXN],rev[MAXN],end[MAXN];
char pat[MAXN];
inline bool judge(int p1, int p2, int len, bool sa){
int w = 0; char *s1 = &pat[p1], *s2 = &pat[p2];
while (w < len && *s1 == *s2) w++, s1++, s2++;
if ((w == len && sa) || *s1 < *s2) return true;
else return false;
}
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}
int main(){
int len = 0; cin>>n;
for (int i=1;i<=n;i++) c[i] = read();
for (int i=1;i<=n;i++) {
pos[i] = len+1; gets(pat+len+1);
len = strlen(pat+pos[i])+pos[i]-1;
end[i] = len;
}
for (int i=1;i<=len;i++) pat[len*2-i+1] = pat[i];
for (int i=1;i<=n;i++) rev[i] = len*2-end[i]+1;
for (int i=1;i<=n;i++) end[i] = end[i] - pos[i] + 1;
memset(f,0x3f,sizeof(f)); f[0][1] = 0; f[1][1] = c[1];
for (int i=2,lim=min(end[i],end[i-1]);i<=n;i++,lim=min(end[i],end[i-1])) {
if (judge(pos[i-1], pos[i], lim, end[i]>=end[i-1])) f[0][i] = min(f[0][i], f[0][i-1]);
if (judge(pos[i-1], rev[i], lim, end[i]>=end[i-1])) f[1][i] = min(f[1][i], f[0][i-1] + c[i]);
if (judge(rev[i-1], pos[i], lim, end[i]>=end[i-1])) f[0][i] = min(f[0][i], f[1][i-1]);
if (judge(rev[i-1], rev[i], lim, end[i]>=end[i-1])) f[1][i] = min(f[1][i], f[1][i-1] + c[i]);
}
LL vout = min(f[0][n], f[1][n]);
cout<<(vout<f[0][MAXN-1]?vout:-1)<<endl;
return 0;
}
I truly appreciate this blog post.Thanks Again. Fantastic.
What’s up mates, its impressive piece of writing concerning cultureand fully
defined, keep it up all the time.
Excellent post but I was wanting to know if you could write
a litte more on this subject? I’d be very thankful
if you could elaborate a little bit more. Thanks!
Hello! This is kind of off topic but I need some advice from an established blog.
Is it very hard to set up your own blog? I’m not very techincal but
I can figure things out pretty quick. I’m thinking about making my
own but I’m not sure where to begin. Do you have any
ideas or suggestions? Thanks
This design is wicked! You 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 loved what you had to say, and more than that, how you
presented it. Too cool!
What’s Taking place i’m new to this, I stumbled upon this I have found It positively helpful and it has helped me out loads.
I hope to give a contribution & aid other customers like its helped me.
Great job.
Good article. I absolutely love this site.
Continue the good work!
Hello there! This is my 1st comment here so I just wanted to give a quick shout out and say I genuinely enjoy reading through your posts.
Can you recommend any other blogs/websites/forums that go over the same topics?
Thanks for your time!
I constantly emailed this webpage post page to all my associates, as
if like to read it afterward my friends will too.
Fascinating blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple tweeks would really make my blog shine.
Please let me know where you got your design. Bless you
A motivating discussion is definitely worth comment.
There’s no doubt that that you should publish more about this
subject, it might not be a taboo subject but usually
folks don’t talk about such subjects. To the next! All the best!!
Wow, amazing blog layout! How long have you been blogging
for? you made blogging look easy. The overall look
of your website is wonderful, let alone the content!
This is really interesting, You are an excessively skilled blogger.
I’ve joined your rss feed and look ahead to in quest of
more of your fantastic post. Also, I have shared your web site in my social networks
My coder is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the costs. But
he’s tryiong none the less. I’ve been using WordPress on various websites for about a year and am worried about switching to another platform.
I have heard fantastic things about blogengine.net. Is there a way
I can transfer all my wordpress content into
it? Any kind of help would be greatly appreciated!
Pretty section of content. I just stumbled upon your weblog and in accession capital to claim that I acquire in fact enjoyed account your weblog posts. Any way I will be subscribing to your feeds and even I fulfillment you get admission to constantly rapidly.
This is very interesting, You are a very skilled blogger.
I’ve joined your rss feed and look forward to seeking more of your wonderful post.
Also, I’ve shared your web site in my social networks!
Thanks for sharing your thoughts. I really appreciate your efforts and I
am waiting for your further write ups thanks once again.
We’re a group of volunteers and opening a new scheme
in our community. Your site offered us with valuable info to
work on. You have done an impressive task and our entire neighborhood can be grateful to
you.
hello there and thank you for your info – I’ve certainly picked up something new
from right here. I did however expertise a few technical points using this website,
as I experienced to reload the web site a lot of times
previous to I could get it to load correctly. I had been wondering if your web hosting is OK?
Not that I’m complaining, but slow loading instances times will very frequently affect your placement in google and could damage your quality score if
ads and marketing with Adwords. Well I am adding this RSS to my e-mail and can look out for much more of your respective fascinating content.
Ensure that you update this again very soon.
Good post. I learn something new and challenging on blogs
I stumbleupon on a daily basis. It’s always exciting to read through content
from other authors and practice something from their websites.
What’s up, this weekend is good for me, for
the reason that this moment i am reading this great informative post here at my house.
Have you ever considered writing an ebook or guest authoring on other websites?
I have a blog based upon on the same information you discuss and would really like to have you share some stories/information. I
know my subscribers would value your work. If you are even remotely interested,
feel free to send me an e-mail.
I think this is among the most vital information for me.
And i’m glad reading your article. But want to remark on few general things, The site style is great,
the articles is really excellent : D. Good job,
cheers
Glad to be one of the visitants on this awesome site : D.
I value the blog post.