「题解」「CF1106E」Lunar New Year and Red Envelopes

一道简单的 动态规划 题。

题目链接：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;
}