【NOIP模拟赛】小奇挖矿 2

2015年10月5日1,8901

原题:streaming_3 noip模拟赛 4和7

【题目背景】

小奇飞船的钻头开启了无限耐久+精准采集模式!这次它要将原矿运到泛光之源的矿石交易市场,以便为飞船升级无限非概率引擎。

【问题描述】

现在有m+1个星球,从左到右标号为0到m,小奇最初在0号星球。

有n处矿体,第i处矿体有ai单位原矿,在第bi个星球上。

由于飞船使用的是老式的跳跃引擎,每次它只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球,小奇会采走该星球上所有的原矿,求小奇能采到的最大原矿数量。

注意,小奇不必最终到达m号星球。

【输入格式】

第一行2个整数n,m。

接下来n行,每行2个整数ai,bi。

【输出格式】

输出一行一个整数,表示要求的结果。

【样例输入】

3 13

100 4

10 7

1 11

【样例输出】

101

【样例解释】

第一次从0到4,第二次从4到11,总共采到101单位原矿。

【数据范围】

对于20%的数据 n=1,m<=10^5

对于40%的数据 n<=15,m<=10^5

对于60%的数据 m<=10^5

对于100%的数据 n<=10^5,m<=10^9,1<=ai<=10^4,1<=bi<=m

题解

对于20%的数据,n=1。只需判断这个星球位置是否能拆分成4和7的和。

可以简单递推,枚举求得。

打表的话可以发现,只有1 2 3 5 6 9 10 13 17不能拆。

对于40%的数据,n很小。可以2^n枚举去哪些星球,然后用上面的方法判定一个星球能否到下一个星球。

对于60%的数据,m比较小。设x[i]为i号星球的原矿数,f[i]为到i号星球能获得的最大原矿数,则f[i]=max{f[i-4],f[i-7]}+x[i]。

对于100%的数据,m很大。

1.将所有矿物排序,f[i]为到第i个矿体能获得的最大原矿数,那么f[i]=max{f[j]}+x[i],其中,i-j满足能拆分成4和7。

这样dp需要n^2的复杂度,但是我们发现,相距超过17的一定可达,那么不超过17的范围内暴力,超过17的取个最大值即可,复杂度O(n)

2.可以把相邻的星球距离超过17的压缩成18,按照60%的做法dp

  • TOT2015年10月6日 下午3:40 回复

    一看就知道是个玩mc的人= =

    #1