一道简单的 动态规划 题。
题目链接:CodeForces 1106E。
CF1106E
题目翻译
新年就要到啦,Bob 打算去要很多红包!不过要红包是一件很费时间的事情。
我们假设从第 $1$ 秒开始共有 $n$ 秒,第 $i$ 个红包可以在第 $s _ i$ 到 $t _ i$ 秒(包括端点)收集,并且其中有 $w _ i$ 元。如果 Bob 拿了第 $i$ 个红包,那么他直到第 $d _ i$ 秒后(不包括 $d _ i$)才可以继续收集红包。其中 $s _ i \leq t _ i \leq d _ i$。
Bob 是一个贪心的人,他贪心地收集红包:如果他在第 $x$ 秒有红包可以收集,他就会选择其中钱最多的那个红包。如果这样的红包有多个,他就选 $d$ 最大的那个红包。如果还是有多个选择,他就随便拿一个。
然而他的女儿 Alice 并不想他的爸爸拿到太多钱。她可以干扰 Bob 最多 $m$ 次。如果 Alice 在第 $x$ 秒干扰 Bob,在这一秒 Bob 就不能收集红包,然后下一秒 Bob 会继续用自己的策略收集。
现在请你求出如果 Alice 采用最优的策略,Bob 能拿到的最少钱数。
数据范围
变量 | 数据范围 |
---|---|
$n$ | $1\leq n\leq 10^5$ |
$m$ | $0\leq m\leq 200$ |
$k$ | $1\leq k\leq 10^5$ |
$w _ i$ | $1\leq w _ i\leq 10^9$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
CodeForces 1106E | $3\text{s}$ | $256\text{MiB}$ |
题解
思路
考虑设 $f _ {i,j}$ 为第 $i$ 个时刻,阻挠 $j$ 次的最小收益,那么我们还需处理出两个数组:
- $g _ i$ 表示 $i$ 时刻如果接到红包后要等到 $g _ i$ 时才能再接红包。
- $h _ i$ 表示 $i$ 时刻如果接到红包可以得到 $h _ i$ 的收益。
那么我们有:
- 不受阻挠:
$$f _ {g _ i,j}=f _ {i,j}+h _ i$$
- 受阻挠:
$$f _ {i+1,j+1}=f _ {i,j}$$
代码
用优先队列预处理 $g _ i,h _ i$,时间复杂度为 $\Theta(n\log _ 2n+nm)$。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define INF 0X3F3F3F3F3F3F3F3F #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=100000+5; const int MAXM=200+5; const int MAXK=100000+5; struct RedBag{ int s,t,d,w; inline void Read(void){ s=read(),t=read(),d=read(),w=read(); return; } inline bool operator>(const RedBag& a)const{ return w==a.w?d>a.d:w>a.w; } inline bool operator<(const RedBag& a)const{ return w==a.w?d<a.d:w<a.w; } }; inline bool cmp(const RedBag& a,const RedBag& b){ return a.s<b.s; } int n,m,K; RedBag R[MAXK]; int g[MAXN],h[MAXN]; ll f[MAXN][MAXM]; priority_queue<RedBag,vector<RedBag>,less<RedBag>/**/> Q; int main(void){ n=read(),m=read(),K=read(); for(reg int i=1;i<=K;++i) R[i].Read(); sort(R+1,R+K+1,cmp); reg int ptr=1; for(reg int i=1;i<=n;++i){ while(R[ptr].s<=i&&ptr<=K) Q.push(R[ptr++]); while(!Q.empty()&&Q.top().t<i) Q.pop(); if(Q.empty()) g[i]=i+1,h[i]=0; else g[i]=Q.top().d+1,h[i]=Q.top().w; } memset(f,0X3F,sizeof(f)); g[0]=1,h[0]=0; f[0][0]=0; for(reg int i=0;i<=n;++i) for(reg int j=0;j<=m;++j){ f[g[i]][j]=min(f[g[i]][j],f[i][j]+h[i]); if(j!=m) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]); } ll ans=INF; for(reg int i=0;i<=m;++i) ans=min(ans,f[n+1][i]); printf("%lld\n",ans); return 0; }
近期评论