小奇挖矿2
【题目背景】
小奇飞船的钻头开启了无限耐久+精准采集模式！这次它要将原矿运到泛光之源的矿石交易市场，以便为飞船升级无限非概率引擎。
【问题描述】
现在有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单位原矿。
【试题分析】
其实看起来没思路，做起来很好做，直接排个序，然后路径压缩即可，代码中解释
【代码】
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct data{
int a,b;
friend bool operator<(data a,data b){
return a.a<b.a;
}
}a[100005];
int n,m;
int v[2000005],f[2000005];//一开始数组木有开大，结果呵呵了
int main()
{
freopen("mining.in","r",stdin);
freopen("mining.out","w",stdout);
memset(f,-1,sizeof(f));
n=read();m=read();
for(int i=1;i<=n;i++)
a[i].b=read(),a[i].a=read();
sort(a+1,a+n+1);//排序
int now=0;
for(int i=1;i<=n;i++)
{
if(a[i].a-a[i-1].a>17)now+=18,v[now]+=a[i].b;
//路径压缩，如果两个相邻星球的距离大于17则就按18来算，然后加上星球的原矿值
else now+=a[i].a-a[i-1].a,v[now]+=a[i].b;
}
int ans=0;
f[0]=0;
for(int i=0;i<=now;i++)
if(f[i]!=-1)
{
f[i+4]=max(f[i+4],f[i]+v[i+4]);//走一步加上一步的原矿值价值
f[i+7]=max(f[i+7],f[i]+v[i+7]);//与上面同理
ans=max(ans,f[now]);
}
printf("%d
",ans);
return 0;
}