P2317 [HNOI2005] 星际贸易

· · 题解

本题的题面很复杂啊……有几个要点需要注意：经过任何一个星球，都必须要进行飞船维护；从一个星球转移到另一个，所消耗的燃料是 2。

第一问很简单。问你最大贸易额是多少，不计一切代价！假设可以完成任务，则第一问答案直接背包即可。

第二问才是难点。数据有一个很好的性质：只有一种获得最大贸易额的方法。这启发我们倒推 DP 状态，就可以找到在哪些星球上卖货。设 g(i,j) 表示到了第 i 个星球，剩余能量是 j，最小代价。考虑两种转移：

1.

g(i,j)\gets \max_{L_k\ge L_i-L_0\land L_k\ge pre}(g(k, j+2)+F_i)

上面这个 pre 的含义是：i 前面最近的一定要卖货的星球。由于 i 星球可能只充能量不卖货，因此要保证一定要经过前一个卖货的星球。

  1. g(i,j)\gets \max(g(i, j), g(i, j-1)+P_i)

这就是在当前星球上充能量的转移。需要保证 P_i>0。

针对第一个转移，k 类似滑动窗口，考虑使用单调队列维护。代码中的单调队列封装成结构体，更好写。

令注：数据范围应该是 R\le 10^7，题面中写错了，已经发送工单。但是最多只会消耗 2n 的能量，取 \min 即可。

再次更新：题面的数据范围已经改对了。

// P2317 [HNOI2005] 星际贸易
#include <cstdio>
#include <iostream>
#include <cstring>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=2005, M=4005, inf=0x3f3f3f3f;
using namespace std;
char buf[1<<21], *p1=buf, *p2=buf;
#define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int x=0, f=1; char c=gc();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=gc();
    while('0'<=c && c<='9') x=(x<<3)+(x<<1)+c-'0', c=gc();
    return x*f;
}

#define no return puts("Poor Coke!"), 0;
int n, m, r, L, a[N], b[N], l[N], p[N], F[N]; bool flag[N];
int f[N][N], g[N][M];
inline void upd(int &x, int y) {x=y>x?x:y;}

struct monoque
{
    struct node {int l, f;} q[N];
    int hh=1, tt;
    inline int query(int x)
    {
        while(hh<=tt && q[hh].l<x) ++hh;
        return hh<=tt?q[hh].f:inf;
    }
    inline void upd(int l, int f)
    {
        while(hh<=tt && q[tt].f>=f) --tt;
        q[++tt]={l, f};
    }
} q[M];

int main()
{
#ifdef Jerrywang
    freopen("E:/OI/in.txt", "r", stdin);
#endif
    n=read(), m=read(), r=read(), L=read(); r=min(r, n+n);
    rep(i, 1, n) a[i]=read(), b[i]=read(), l[i]=read(), p[i]=read(), F[i]=read();
    rep(i, 1, n) if(l[i]-l[i-1]>L) no
    memset(f, -0x3f, sizeof f);
    f[0][0]=0;
    rep(i, 1, n)
    {
        rep(j, 0, m) 
        {
            f[i][j]=f[i-1][j];
            if(j>=a[i]) f[i][j]=max(f[i][j], f[i-1][j-a[i]]+b[i]);
        }
    }
    int mxj=0;
    rep(j, 1, m) if(f[n][j]>f[n][mxj]) mxj=j;
    int j=mxj;
    for(int i=n; i; i--)
    {
        if(j>=a[i] && f[i][j]==f[i-1][j-a[i]]+b[i])
            j-=a[i], flag[i]=1;
    }
    memset(g, 0x3f, sizeof g);
    g[0][r]=0; q[r].upd(0, 0);
    int pre=0;
    rep(i, 1, n)
    {
        rep(j, 0, r)
        {
            if(p[i] && j) upd(g[i][j], g[i][j-1]+p[i]);
            int lo=max(pre, l[i]-L);
            upd(g[i][j], q[j+2].query(lo)+F[i]);
            q[j].upd(l[i], g[i][j]);
        }
        if(flag[i]) pre=l[i];
    }
    int res2=inf;
    rep(j, 0, r) upd(res2, g[n][j]);
    if(res2==inf) no
    printf("%d %d", f[n][mxj], f[n][mxj]-res2);

    return 0;
}