首页 > 其他 > 详细

【JZOJ】3490. 旅游题解报告

时间:2019-08-21 20:19:46      阅读:85      评论:0      收藏:0      [点我收藏+]

题目

技术分享图片

技术分享图片

技术分享图片


思路

这道题看上去就像一个动态规划!但是还是要把矩阵压成一行。

然后按 \(A\)数组 将结构体从小到大排个序。

随后我们开始了动规标准步骤:

确定状态

很显然\(f_i\) 表示游览完第\(~i~\)个景点是的最长时间。

Q(动规小白为啥动规小白要做这题啊):怎么看粗来的???

A:动规不是一维不行加一维的吗

确定转移方程

有了这个状态相信动规小白也能看粗来转移方程吧!

那么我们假设看完了第\(j\)个景点后就去了第\(i\)个景点(\(j~ \rightarrow ~i\))。

那么我们的方程就显而易见了。

\[\begin{matrix}f_i = max\{ f_j + (abs(x_i - x_j) + abs(y_i-y_j))) \}+b_i\\ =max\{ f_j + dis(i, j)\}+B_i~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\end{matrix}\]

温馨提示:

可以发现直接暴力这么做的时间复杂度是\(O((nm)^2)\)

即使我们的题目限时两秒也会炸!!!

Q:怎么办呢???

\[\Large\text{卡常!!!}\]

1、

如果\(j\)直接从\(1\)开始枚举就会有冗余的情况:

假设你的\(A_i\)\(4\)
\(A_{1 \~ i-1}\)分别是\(\{ 1,1,1,1,1,2,2,2,3 \}\)
你肯定选\(3\)都要比选其他的数要强(请读者自行理解),所以从\(3\)的那里开始

2、

‘register‘走起。。。

【JZOJ】3490. 旅游题解报告

原文:https://www.cnblogs.com/GJY-JURUO/p/11390706.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!