[CSP-S模拟测试]:小奇挖矿2（DP+赛瓦维斯特定理）

题目背景

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

题目描述

现在有$m+1$个星球，从左到右标号为$0$到$n$，小奇最初在$0$号星球。
有$n$处矿体，第$i$处矿体有$a_i$单位原矿，在第$b_i$个星球上。
由于飞船使用的是老式的跳跃引擎，每次它只能从第$x$号星球移动到第$x+4$号星球或$x+7$号星球。每到一个星球，小奇会采走该星球上所有的原矿，求小奇能采到的最大原矿数量。
注意，小奇不必最终到达$m$号星球。

输入格式

第一行$2$个整数$n$，$m$。
接下来$n$行，每行$2$个整数$a_i$，$b_i$。

输出格式

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

样例

样例输入：

3 13
100 4
10 7
1 11

样例输出：

101

数据范围与提示

样例解释：

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

数据范围：

对于$20\%$的数据$n=1$，$m\leqslant {10}^5$。
对于$40\%$的数据$n\leqslant 15$，$m\leqslant {10}^5$。
对于$60\%$的数据$m\leqslant {10}^5$。
对于$100\%$的数据$n\leqslant {10}^5$，$m\leqslant {10}^9$，$1\leqslant a_i\leqslant {10}^4$，$1\leqslant b_i\leqslant m$。

题解

依然是观察数据范围，发现$60\%$的$DP$很好打，定义$dp[i]$表示到了$i$的最大原矿数量，那么状态转移方程也很简单：$dp[i]=\max(dp[i-4],dp[i-7])+x[i]$，式中$x[i]$表示$i$点的原矿数量为$x[i]$。

但是显然对于$100\%$的数据无论是时间还是空间都是不允许的，所以考虑进行优化。

这时候你的思路很可能就想到了某种玄学的数据结构，但是如果你做过$NOIP\ 2017\ D1T1$小凯的疑惑的话，你可能就乐了。

没错，这道题也涉及到了赛瓦维斯特定理。

我们会发现，仅$4$和$7$两个数字最大的不能组成的数字为$4\times 7-4-7=17$，那么所有大于$17$的数字都是能由$4$和$7$通过加减凑出来的，于是我们可以考虑离散化，之后两点大于$17$的就将其距离付成$18$即可，考场上有好多同学打了一种会被卡的方法，但是$A$了这道题，然而这种做法不会被卡，应该是这道题最严谨的一种做法了。

时间复杂度：$\Theta(18\times n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

pair<int,int> pos[100010];

int delta[100010];

int dp[2000010];

int Map[2000010];

int p;

int ans;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		int a,b;

		scanf("%d%d",&a,&b);

		pos[i]=make_pair(b,a);

	}

	sort(pos+1,pos+n+1);

	memset(dp,-0x3f,sizeof(dp));

	dp[0]=0;

	for(int i=1;i<=n;i++)

		delta[i]=min(18,pos[i].first-pos[i-1].first);

	for(int i=1;i<=n;i++)

	{

		p+=delta[i];

		Map[p]+=pos[i].second;

	}

	for(int i=4;i<=p;i++)

	{

		dp[i]=max(dp[i],dp[i-4]+Map[i]);

		if(i>6)dp[i]=max(dp[i],dp[i-7]+Map[i]);

	}

	for(int i=1;i<=p;i++)ans=max(ans,dp[i]);

	cout<<ans<<endl;

	return 0;

}

rp++

巴特西