CH Round#48 T2 4和7 | 首都客運時刻表查詢網
![CH Round#48 T2 4和7](https://i.imgur.com/2oxSoeJ.png)
神犇告诉了做法最后还是跪掉……好多细节问题……这道题一个朴素的想法当然是O(m)的DP……但是m的范围告诉你想要100分必须得想与m无关的算法……通过打表发现(==囧)…
![CH Round#48 T2 4和7](https://i.imgur.com/2oxSoeJ.png)
神犇告诉了做法最后还是跪掉……好多细节问题……这道题一个朴素的想法当然是O(m)的DP……但是m的范围告诉你想要100分必须得想与m无关的算法[1]……通过打表发现(= =囧)……从第18个格子开始,都是可以从起点0处出发到达的……所以只需记录下前17个格子是否能达到(即该数能否由4和7组成),这里我用c数组储存打好的表,c[i]代表第i个格子能否到达。
然后对读入的数据以格子的先后为关键字排序(显然题目保证b[i]都不相同)
接着对这n堆药扫一遍。对于第i堆药,再来从后往前枚举,如果找到b[i]-b[j]<18的就判断能否转移,然后更新f[i]的值。
直到发现b[i]-b[j]>=18,这时候再前面的的肯定是可以转移的。
那么我们定义mx[i]为f[1]到f[i]中的最大值,即mx[i]=max(f[1],f[2]...f[i])。那么此时只需要取mx[j]来更新即可。
注意到i是从前往后枚举,那么只需要在每次i++以后更新mx[i]即可,这样可以保证之后的枚举i时,之前的j(0<=j<=i)是存在mx[j]的。。。
还要注意一个特判(就是我SB的地方)。如果前面b[i]-b[j]<18的枚举完了,发现j为0时。这时候并不是b[i]-b[j]>=18导致的了。。。所以这时候必须要判断j能否到达i,或者b[i]-b[j]>=18两者满足其一即可。不然就不能更新……
然后因为最后停下来的位置可以是任意位置,所以输出mx[n]。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<set> #include<queue> #include<stack> #incl...