「Codeforces 1106E」Lunar New Year and Red Envelopes

发表于 | | 阅读次数:
字数统计: 1k 字

Description

题目链接：Codeforces 1106E

新年就要到了，Bob 想要收到很多红包！不过收集红包是一件很费时间的事情。

假设从第 $1$ 秒开始共有 $n$ 秒，一共有 $k$ 个红包，其中第 $i$ 个红包可以在第 $s_i$ 到 $t_i$ 秒（包括端点）收集，并且其中有 $w_i$ 元。如果 Bob 选择拿第 $i$ 个红包，他只能在 $s_i$ 到 $t_i$ 中的一个整数时刻收集，并且他在 $d_i$（包括）时刻前不能收集任何红包。保证 $s_i\le t_i\le d_i$。

Bob 是一个贪心的人，他贪心地收集红包——如果他在第 $x$ 秒有红包可以收集，他会选择其中钱最多的那个红包。如果这样的红包也有多个，他会选择其中 $d$ 最大的那个红包。如果仍然有多个选择，Bob 会在其中随便拿一个。

但是，他的女儿 Alice 不想让她的父亲得到太多的钱。她可以在整数时刻干扰 Bob 最多 $m$ 次。如果 Alice 打算在时刻 $x$ 干扰 Bob，那么他不就能在时刻 $x$ 收集红包，然后在时刻 $x+1$ 恢复通常的策略（没有干扰时这一秒的策略），这可能会使得他丢失一些红包。

如果 Alice 采用最优策略，请计算出 Bob 能拿到的最少的钱数。

数据范围：$1\le n,k\le 10^5$，$0\le m\le 200$，$1\le s_i\le t_i\le d_i\le n$，$1\le w_i\le 10^9$

Solution

题目中有一个非常重要的句子：

在时刻 $x+1$ 恢复通常的策略。

换言之：无论是否干扰，对于任意的 $i$，Bob 在第 $i$ 秒的策略是固定的！

那么我们可以预处理出第 $i​$ 秒的策略，得到他在这一秒操作的收益和下一次操作的时间（如果不操作，则收益为 $0​$，下一次时间为 $i+1​$）。设计 $\text{DP}​$ 状态 $f_{i,j}​$ 表示第 $i​$ 秒之前干扰 $j​$ 次可以获得的最小钱数。转移方程如下（向后更新）：

  • 如果第 $i​$ 秒干扰：$f_{i,j}\rightarrow f_{i+1,j+1}​$。
  • 如果第 $i$ 秒不干扰：$f_{i,j}+\text{第}\ i\ \text{秒的收益}\rightarrow f_{\text{第}\ i\ \text{秒后下一次操作的时间},j}$

最后的答案为 $\min_{0\le i\le m}\{f_{n+1,i}\}$。

分析好 $\text{DP}$，我们又该如何预处理呢？

先把所有的红包按照起始时间 $s_i$ 从小到大排序。然后枚举所有的时间点，将起始时间在 $i$ 之前的红包都提出来，得到满足条件的红包（第一关键字 $w$ 最大，第二关键字 $d$ 最大）。这个查找过程可以通过优先队列或者线段树来实现，但是要注意一些细节问题。

时间复杂度：$O(n\log k+nm)$

Code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=1e5+5,M=205;
int n,m,k,nxt[N],val[N];
long long f[N][M];
struct Data {
    int s,t,d,w;
    bool operator < (const Data &b)const {
        return s<b.s;
    }
    bool operator > (const Data &b)const {
        return w==b.w?d<b.d:w<b.w;
    }
} a[N];

void chkmin(long long &x,long long y) {
    x=x<y?x:y;
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i) scanf("%d%d%d%d",&a[i].s,&a[i].t,&a[i].d,&a[i].w);
    std::sort(a+1,a+k+1);
    std::priority_queue<Data,std::vector<Data>,std::greater<Data> > q;
    for(int pos=1,i=0;i<=n;++i) {
        while(pos<=k&&a[pos].s<=i) q.push(a[pos++]);
        while(!q.empty()) {
            Data u=q.top();
            if(u.t>=i) {
                nxt[i]=u.d+1,val[i]=u.w;
                break;
            } else {
                q.pop();
            }
        }
        if(!nxt[i]) nxt[i]=i+1,val[i]=0;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<=n;++i) for(int j=0;j<=m;++j) {
        chkmin(f[i+1][j+1],f[i][j]);
        chkmin(f[nxt[i]][j],f[i][j]+val[i]);
    }
    long long ans=1LL<<60;
    for(int i=0;i<=m;++i) chkmin(ans,f[n+1][i]);
    printf("%lld\n",ans);
    return 0;
}
0%