M_sea

CF1106E Lunar New Year and Red Envelopes
CodeforcesLuogu翻译分析这种sbt我考场竟然没写出来...首先每秒选的红包的$d$和$w$是确定的。...
扫描右侧二维码阅读全文
07
2019/02

CF1106E Lunar New Year and Red Envelopes

Codeforces

Luogu翻译

分析

这种sbt我考场竟然没写出来...

首先每秒选的红包的$d$和$w$是确定的。这个非常显然。

然后可以预处理出每秒所选红包的$d$和$w$。可以用线段树或者堆来搞一下。

设$f[i][j]$表示前$i$秒,干扰了$j$次的最小钱数。

然后转移:

  • 干扰:$f[i][j]\to f[i+1][j+1]$
  • 不干扰:$f[i][j]+w[i]\to f[d[i]+1][j]$

然后,可能有的时刻没有红包捡,这时的转移是$f[i][j]\to f[i+1][j]$。

边界是$f[0][0]=0$,答案是$\max\limits_{i=0}^mf[n+1][i]$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

template<typename T>
inline void chkmin(T& x,T y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int M=200+10;

int n,m,k;
struct Redbag { int s,t,d,w; } a[N];
bool operator <(Redbag a,Redbag b) { return a.w>b.w||(a.w==b.w&&a.d>b.d); }
bool operator >(Redbag a,Redbag b) { return b<a; }
inline int cmp(Redbag a,Redbag b) { return a.s<b.s; }
priority_queue<Redbag,vector<Redbag>,greater<Redbag> > Q;
int d[N],w[N];
ll f[N][M];

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=k;++i)
    a[i].s=read(),a[i].t=read(),a[i].d=read(),a[i].w=read();
    sort(a+1,a+k+1,cmp);
    for (re int i=1,j=0;i<=n;++i) {
        while (j<k&&a[j+1].s<=i) Q.push(a[++j]);
        while (!Q.empty()&&Q.top().t<i) Q.pop();
        if (!Q.empty()) d[i]=Q.top().d,w[i]=Q.top().w;
    }
    memset(f,0x3f,sizeof(f)); f[0][0]=0;
    for (re int i=0;i<=n;++i)
    for (re int j=0;j<=m;++j) {
        chkmin(f[i+1][j+1],f[i][j]);
        if (d[i]) chkmin(f[d[i]+1][j],f[i][j]+w[i]);
        else chkmin(f[i+1][j],f[i][j]);
    }
    ll ans=2e18;
    for (re int i=0;i<=m;++i) chkmin(ans,f[n+1][i]);
    printf("%I64d\n",ans);
    return 0;
}
最后修改:2019 年 02 月 07 日 08 : 39 PM

2 条评论

  1. smy

    您不是说可以直接线段树吗qwq

    1. M_sea
      @smy

      太码了,不想写的说

发表评论