emm,这次的真的不简单的,T3比T4难?
醉了。。。
蒟蒻肯定没有其他大佬讲的好啊,但肯定尽力,真的敲得呕心沥血,求过 。纪念写出的一道比较经典的线性动规。
分析题意,我(以弱者的角度先看问题) 首先想到的是:排序+贪心。本以为今天如此简单,结果发现是自己太天真了。。。然而之后发现:并不一定要一次接着一次的发车,所以贪心破产。
之后就有点摸不着头脑,去打了T4,出于宣泄直接上爆搜,惊奇的发现样例过了,赶快开心的回来再看T3.
这时候就想:普及深搜,模拟,签到都出了,这道题多半就是动规了吧,于是,扯了这么一大堆下面进入正题。
思路:动规+前缀和(但据某些大佬说还可以用斜率优化?在这里很抱歉我太弱而不会)。
首先我们直切核心——状态转移方程。
我们可以设f[i]f[i]f[i]表示i时间前所有人的最小等待时间。
PS:在这里如果不好确定方程的维数怎么办?可以结合数据范围和空间限制来考虑(多半是,虽然这题好像也可以有二维与t无关的数组)。
我们可以把每个人的时间都标在一条时间轴上。然后能更直观的理解。
这里借用@sooke 大佬的一张图。
我们假设发车时间为每个来回4min,各位等车的同学如图中蓝点所示。
然后我们假设当前要求的f[i]f[i]f[i]中的i=11i=11i=11,于是下面开始分析。
我们可以发现:如果之前的都已经算出的话,那么状态转移方程可如下所示:
其中cnt[i]cnt[i]cnt[i]代表第i时间到达车站的同学的人数,sum[i]sum[i]sum[i]代表第i时间到达车站的同学的时间的总和。
jjj即为上一辆车的发车时间。
刚开始我们对于j的范围,应该能想到是:
很明显的( ⊙ o ⊙ )!j的取值只要小于i并且和i相聚一个往返时间不就行了吗?
然后的结果是:50分。(官方数据亲测)
但是noip都结束了呀同志,我们不能只局限于50分呀!
所以进行改进:
这时候我们又想:可不可以将j的范围进一步缩小呢?
但其实是肯定可以的。我们发现j可以:
为什么呢?因为如果两车间的相距时间大于了一趟往返的时间,那么我们完全可以在两者中间继续分割,并不影响原来的答案。
这个时候也是大大的提升了程序的速度,然而:70分(官方数据亲测)
泪奔~
and then ,我们可以继续考虑有没有什么可以剪去的无用状态。
仔细研究发现:当两次发车之间如果没有需要等待的同学的话,直接跳过即可。
经过改正:100分(官方亲测)
转载于:https://www.cnblogs.com/vercont/p/10210037.html
相关资源:JAVA上百实例源码以及开源项目