hzwer7629 | 小奇挖矿 2

Portal

对于 60% 的数据,可以直接写出状态转移方程:
fi=max{fi4,fi7}+aif_i=\max {f_{i-4},f_{i-7}} +a_i

然后当成普通的一维 DP 做可以拿下 60pts。

对于 100% 的数据,由于 m109m\leq 10^9 如果直接用数组记录每个点的收益显然会 MLE。打表找规律可知(我怎么知道要打表 (ノ`Д) ノ),当 PiP_i 可到达时,[Pi+17,Pm]\left[P_i+17,P_m\right] 均可到达。那么可以考虑把在每个有收益的位置 18 个单位后的位置的收益全部累加到第 18 个位置,最终数组大小控制在 26 左右,再套上 60pts 的做法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using std::max;
const int N=2e6+2;int a[N],f[N];
struct uuz {
int val,pos;
friend bool operator < (uuz& a,uuz& b) {return a.pos<b.pos;}
}mine[N];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
int main() {
int n=read(),fp=0,ans=0;read();
for(int i=1;i<=n;++i) mine[i]=(uuz){read(),read()};
std::sort(mine+1,mine+1+n);memset(f,128,sizeof(f));f[0]=0;
for(int i=1;i<=n;++i)
if(mine[i].pos>=mine[i-1].pos+18) a[fp+=18]+=mine[i].val;
else a[fp+=mine[i].pos-mine[i-1].pos]+=mine[i].val;
for(int i=0;i<=fp;++i)if(f[i]>=0) {
f[i+4]=max(f[i+4],f[i]+a[i+4]);
f[i+7]=max(f[i+7],f[i]+a[i+7]);
}
printf("%d",max(ans,f[fp]));
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。