题解 CF1430F 【Realistic Gameplay】

· · 题解

这题似乎是有O(n)做法的。。。当然O(n^2)也能过就是了。

贪心不太好做。

其实是不会贪心

考虑一个最暴力的dp。设f[n][m]表示递推到第n项，剩余m颗子弹所需要耗费的子弹，与已经丢弃掉的子弹。

这个dp看似有O(nk)项，但是仔细分析一下，可以发现：对于一个状态f[i][j]，转移只有两种可能。要么用这j个子弹打完第i波怪物后，重新装弹；要么不重新装弹，继续使用剩下的子弹攻击。这样只会转移到f[i+1][J]与f[i+1][K]。J可以方便地计算出来。

所以每次递推只会多产生1种状态，总状态就是O(n^2)，复杂度O(n^2logn)。

/*************************************************************************
    > File Name: f.cpp
    > Author: The-Out-Land
    > Mail: [email protected] 
    > Created Time: 2020年10月11日 星期日 16时52分34秒
 ************************************************************************/

#include <bits/stdc++.h>

#define enter putchar('\n')
#define space putchar(' ')
#define re register
#define N 2010
#define int long long
#define fi first
#define se second

using namespace std;

const int inf=0x1f3f3f3f3f3f3f3f;

inline int max(int x,int y){return (x>y?x:y);}

inline int min(int x,int y){return (x<y?x:y);}

inline int read(){
    int x=0;char c=getchar();bool y=1;
    for(;c<'0' || c>'9';c=getchar()) if(c=='-') y=0;
    for(;c>='0' && c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
    if(y) return x;
    return -x;
}

int n,K,cnt,pre,fans;

struct data{
    int l,r,val;
    data(const int X=0,const int Y=0,const int Z=0):l(X),r(Y),val(Z){}
}a[N],B;

map<int,int> f[N],Q;

bool cmp(const data &x,const data &y){return x.l==y.l?x.r<y.r:x.l<y.l;}

inline void Input(){
    n=read(),K=read();
    for(re int i=1;i<=n;++i){
        B.l=read(),B.r=read(),B.val=read();
        if(B.l==B.r)    Q[B.l]+=B.val;
        else            a[++cnt]=B;
    }
    for(auto i:Q){
        a[++cnt]=data(i.fi,i.fi,Q[i.fi]);
    }
    sort(a+1,a+cnt+1,cmp);
    n=cnt;
    return;
}

inline void solve(){
    f[0][K]=0;
    int now;
    for(re int i=1;i<=n;++i){
        pre=i-1;
        f[i][K]=inf;
        for(auto J:f[pre]){
            int j=J.fi,V=J.se;
            if(V==inf) continue;
            if(j+(a[i].r-a[i].l)*K<a[i].val) continue;
            if(j>=a[i].val){
                if(f[i].find(j-a[i].val)==f[i].end())
                f[i][j-a[i].val]=inf;
                f[i][j-a[i].val]=min(f[i][j-a[i].val],V+a[i].val);
                if(a[i+1].l!=a[i].l)
                f[i][K]=min(f[i][K],V+j);
                continue;
            }
            now=(K-(a[i].val-j)%K)%K;
            if(f[i].find(now)==f[i].end()) f[i][now]=inf;
            if(j+max(0ll,a[i].r-a[i].l-1)*K>=a[i].val || a[i+1].l!=a[i].r){
                if(a[i+1].l!=a[i].l)
                f[i][K]=min(f[i][K],V+now+a[i].val);
                f[i][now]=min(f[i][now],V+a[i].val);
            }
            else{
                f[i][now]=min(f[i][now],V+a[i].val);
            }
        }

        /*printf("%lld\n",i);
        for(auto J:f[i]) printf("%lld %lld\n",J.fi,J.se);*/
        if(f[i].empty()) return puts("-1"),void();
        pre=i;
    }

    fans=inf;
    for(auto i:f[n])    fans=min(fans,f[n][i.fi]);
    if(fans==inf)       return puts("-1"),void();
    cout<<fans<<endl;
    return;
}

signed main(){
    //freopen("data.in","r",stdin);
    Input();
    solve();
    return 0;
}