相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解：http://www.cnblogs.com/clrs97/p/4675155.html
解题报告
我们发现一条路径的长度为$ax+b$，是一条直线的形式
那么我们如果求出所有直线的凸包，那么就可以$O(n)$计算答案了
现在考虑如何搞出凸包：
若两条直线的斜率相等，那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点，斜率为$j$，的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来，之后我们显然可以$O(n)$构造出凸包了
有了凸包后，每一条线段的贡献就是一个等差数列，这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$
I really enjoy the blog. Will read on…
Awesome blog post.Much thanks again. Awesome.
I really enjoy the article post. Really Great.
Major thanks for the blog post.Really looking forward to read more. Great.
Wow, great post.Much thanks again. Keep writing.
I really like and appreciate your post.Thanks Again. Great.
Really enjoyed this blog article.Really looking forward to read more. Keep writing.
I cannot thank you enough for the article.Much thanks again. Want more.
I really liked your blog article.Really thank you!
Muchos Gracias for your post.Really thank you! Great.
This is one awesome article. Fantastic.
I really like and appreciate your blog. Much obliged.
Thanks a lot for the blog article.Much thanks again. Awesome.
Very good blog post.Thanks Again. Will read on…
Muchos Gracias for your blog article. Awesome.
Very neat article.Really thank you!
Thanks for sharing, this is a fantastic article post.Much thanks again.
I’m very happy to find this great site. I wanted to thank you for your time for this fantastic read!!
I definitely appreciated every bit of it and I have you saved as
a favorite to see new information in your web site.
I’ve learn a few excellent stuff here. Certainly worth bookmarking for revisiting.
I surprise how so much attempt you put to create any such excellent informative web site.
Great article post.Really thank you! Cool.
I am in fact grateful to the owner of this web site who has shared
this fantastic article at at this place.
Thanks a lot for the post.Thanks Again. Awesome.
An intriguing discussion is definitely worth comment. There’s no doubt that that
you should write more on this issue, it
might not be a taboo matter but generally people do not speak about these topics.
To the next! Kind regards!!
Really enjoyed this blog post. Want more.
Really enjoyed this article post.Much thanks again. Will read on…
A big thank you for your post.Thanks Again. Awesome.
Very informative article post.Thanks Again. Fantastic.
Fantastic goods from you, man. I’ve take note your stuff prior to and you’re simply extremely magnificent.
I actually like what you’ve bought here,
really like what you are saying and the best way during which you assert it.
You are making it enjoyable and you still care for to keep it sensible.
I can not wait to learn far more from you.
This is really a wonderful website.
Thanks for sharing, this is a fantastic blog post.Really looking forward to read more. Keep writing.
Enjoyed every bit of your article post.Really thank you! Cool.
I really enjoy the blog post. Fantastic.
Thank you for your blog post.Really thank you! Really Cool.
An impressive share! I have just forwarded this onto a co-worker who had been doing a little research on this.
And he actually ordered me breakfast because I discovered it
for him… lol. So let me reword this…. Thanks for the
meal!! But yeah, thanx for spending time to
discuss this issue here on your internet site.
Im thankful for the post.Much thanks again. Really Great.
Great blog post.Much thanks again. Great.
We’re a bunch of volunteers and starting a new scheme in our community.
Your web site offered us with useful info to work on. You have performed an impressive
task and our whole neighborhood will probably be thankful to you.
Thank you ever so for you post.
I really like and appreciate your blog.Thanks Again. Keep writing.
Say, you got a nice article post.Much thanks again. Fantastic.
I really like and appreciate your blog.Thanks Again. Much obliged.
Wow, great blog article.Really looking forward to read more. Much obliged.
Very neat blog post.Really thank you! Want more.
Im grateful for the blog post.Really looking forward to read more. Awesome.
Major thanks for the article.Really looking forward to read more. Cool.
Thanks-a-mundo for the blog post.Much thanks again. Really Great.
Having read this I thought it was extremely enlightening.
I appreciate you finding the time and energy to put this article together.
I once again find myself spending way too much time both reading and
leaving comments. But so what, it was still worth it!
Very neat blog article.Really looking forward to read more. Keep writing.
I really like and appreciate your blog.Thanks Again. Fantastic.
This is very fascinating, You are an overly professional blogger.
I’ve joined your rss feed and look forward to seeking more of your wonderful post.
Additionally, I’ve shared your web site in my social networks
Very neat blog article.Much thanks again. Awesome.
Thanks for the blog post. Really Cool.
Appreciate you sharing, great article.Really thank you! Really Cool.
I really liked your article post. Awesome.
I really like reading an article that can make men and women think.
Also, many thanks for allowing me to comment!
Having read this I thought it was very informative.
I appreciate you taking the time and effort to put this
information together. I once again find myself personally spending way too much time both reading and leaving comments.
But so what, it was still worth it!
What’s Going down i am new to this, I stumbled upon this I’ve discovered It positively helpful and it has aided me out loads. I am hoping to contribute & help other customers like its aided me. Good job.
wow, awesome blog article.Really thank you! Much obliged.
Thanks for sharing, this is a fantastic article post.Thanks Again. Great.
Great, thanks for sharing this blog article.Really looking forward to read more. Keep writing.
Major thankies for the blog article.Really looking forward to read more. Cool.
Im obliged for the article post.Thanks Again. Fantastic.
Very good post. Cool.
Thank you for your article.Thanks Again.
Im grateful for the article post.Really thank you! Really Cool.
I truly appreciate this blog.Really looking forward to read more. Much obliged.
Thanks for the blog article.Really thank you! Much obliged.
Thanks a lot for the blog. Will read on…
Thanks again for the post.
Thanks-a-mundo for the blog.Really thank you! Great.
Usually I do not read post on blogs, but I would like to say that this write-up very compelled me to take a look at
and do so! Your writing taste has been surprised me.
Thanks, very great post.
Howdy I am so glad I found your site, I really found you by accident, while I was looking on Digg for something else, Anyhow
I am here now and would just like to say thanks for a tremendous post and a all round exciting blog (I also
love the theme/design), I don’t have time to look over it all at the moment
but I have book-marked it and also included your RSS feeds,
so when I have time I will be back to read much more, Please do keep up the excellent b.
Hello, I check your blogs like every week. Your story-telling style is witty, keep it up!
A round of applause for your post.Really looking forward to read more.
Very neat blog post.Much thanks again. Awesome.
Thank you for your article. Awesome.
Appreciate you sharing, great article post.Thanks Again. Will read on…
Thanks for sharing, this is a fantastic article post.Thanks Again. Cool.
wow, awesome article.Much thanks again.
A big thank you for your article post.Really thank you! Really Cool.
Appreciate you sharing, great blog.Really thank you! Awesome.
Thanks a lot for the blog post. Keep writing.
I cannot thank you enough for the article.Really looking forward to read more.
Very good blog post.Really thank you!
Hey, thanks for the blog post.Really thank you! Really Cool.
It’s impressive that you are getting thoughts from this
paragraph as well as from our argument made at this time.
Hey, thanks for the blog.
Wow, great post.Thanks Again. Awesome.
I think this is a real great blog.Much thanks again. Keep writing.
I loved your blog post.Really thank you! Really Great.
Thanks a lot for the blog post.Much thanks again.
A round of applause for your article post.Much thanks again. Much obliged.
Thanks a lot for the article post.Really thank you! Much obliged.
Im grateful for the blog post. Really Great.
What’s up, I would like to subscribe for this webpage to take most recent
updates, therefore where can i do it please help out.
Thanks for sharing, this is a fantastic blog post.Really thank you! Will read on…
Thanks for sharing, this is a fantastic post.Much thanks again.
Muchos Gracias for your blog article.Really thank you! Much obliged.
A big thank you for your article.Really thank you! Cool.
I cannot thank you enough for the article post.Really looking forward to read more. Keep writing.
Hey, thanks for the article post.Thanks Again. Really Great.
Im thankful for the article.Really looking forward to read more. Much obliged.
Really informative article.Thanks Again. Awesome.
wow, awesome blog.Really looking forward to read more. Really Great.
Hey, thanks for the article.
I really like and appreciate your blog post.Thanks Again. Much obliged.
Hey, thanks for the post.Really thank you! Will read on…
Great article.Much thanks again. Want more.
Wow, that’s what I was exploring for, what a information!
existing here at this website, thanks admin of this web site.
Say, you got a nice article post.Thanks Again. Keep writing.
A round of applause for your blog post.Thanks Again. Cool.
Thanks a lot for the blog. Cool.
Wow, great blog.Much thanks again. Really Cool.
Great article.Really looking forward to read more. Want more.
Im grateful for the post.Thanks Again. Much obliged.
Major thanks for the post. Keep writing.
Enjoyed every bit of your post.Really looking forward to read more. Fantastic.
Major thankies for the blog post.Really thank you! Really Cool.
Very informative article post.Really looking forward to read more. Want more.
Hey, thanks for the blog post.Much thanks again. Great.
Thank you for your post.Really looking forward to read more. Really Cool.
Muchos Gracias for your blog.Thanks Again. Want more.
Fantastic article. Great.
Im obliged for the post.Really looking forward to read more. Want more.
Thanks so much for the blog.Much thanks again. Cool.
A round of applause for your post.Really thank you!
wow, awesome blog article.Thanks Again. Fantastic.
Just desire to say your article is as surprising. The clearness to your put up
is simply nice and i can assume you’re knowledgeable on this subject.
Well with your permission let me to grab your RSS feed
to keep updated with coming near near post. Thanks one million and please continue the
rewarding work.
I cannot thank you enough for the blog.Thanks Again.
I cannot thank you enough for the article post. Great.
I truly appreciate this article post. Awesome.
I really like and appreciate your blog post. Great.
I loved your blog post.Really looking forward to read more. Really Great.
Very neat blog post.Thanks Again. Want more.
I truly appreciate this blog article. Keep writing.
Terrific paintings! That is the type of info that are supposed to be shared across the internet. Shame on Google for not positioning this publish higher! Come on over and seek advice from my website . Thanks =)
Im obliged for the post.Much thanks again. Want more.
I truly appreciate this post.Really thank you! Really Cool.
Thanks a lot for the article post.Really thank you! Keep writing.
I loved your blog article.Thanks Again. Much obliged.
Say, you got a nice blog post.Really looking forward to read more. Cool.
I value the blog post.Thanks Again. Keep writing.
Im thankful for the blog article.Thanks Again. Want more.
Im obliged for the article post.Much thanks again. Really Great.
Thanks for the blog.
Im thankful for the blog article.Much thanks again. Want more.
Im grateful for the article post.Much thanks again. Much obliged.
Really appreciate you sharing this article.Thanks Again. Fantastic.
Im obliged for the post.Really thank you! Fantastic.
Awesome blog post.Really thank you! Fantastic.
I appreciate you sharing this article.Really thank you!
I am so grateful for your article post.Really thank you! Really Great.
Im grateful for the post.Really thank you! Really Great.
Very good post.Really thank you! Fantastic.
Thanks so much for the blog article.Much thanks again. Really Cool.
Thanks for the article post.Really thank you! Awesome.
Im grateful for the article post.Thanks Again.
Major thanks for the article post. Cool.
I value the article post.Much thanks again. Cool.
Really informative article post.Really looking forward to read more. Will read on…
Say, you got a nice blog article.Really looking forward to read more. Really Cool.
I value the blog.Really thank you! Want more.
Im grateful for the article post.Really looking forward to read more. Want more.
Im obliged for the article post.Really looking forward to read more. Great.
Awesome blog post.Really looking forward to read more. Really Great.
Major thanks for the article post.Really thank you! Great.
I appreciate you sharing this post.Really thank you! Much obliged.
Very neat post.Thanks Again. Much obliged.
This is one awesome article.Really thank you! Great.
Im grateful for the post.Thanks Again. Want more.
This is one awesome blog article.Really looking forward to read more.
Say, you got a nice article.Thanks Again. Want more.
Really informative article post.Really thank you! Much obliged.
Very informative blog article. Fantastic.
I really like and appreciate your blog.Much thanks again. Cool.