题目概述

HDU3842

解题报告

先按 $D$ 排个序，然后不难想到DP（注意，根据题目要求 $f_j$ 必须 $\ge 0$ ）：

$$ f_i=\max\{f_j+(D_i-D_j-1)G_j+R_j-P_i|f_j\ge 0\} $$

考虑斜率优化（ $j<k<i$ ）：

$$ f_j+(D_i-D_j-1)G_j+R_j-P_i\ge f_k+(D_i-D_k-1)G_k+R_k-P_i\\ f_j-D_jG_j-G_j+R_j-(f_k-D_kG_k-G_k+R_k)\ge D_i(G_k-G_j) $$

问题来了，我们排序只保证了 $D$ 有序，$G$ 还是乱序的，因此我们不能用单调队列来做，我们需要维护上凸壳。

显然可以用set维护，但是还可以用更简单的方法：cdq分治。我们利用已经求出的左半边建出上凸壳，然后更新右半边即可。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef long long LL;typedef long double DB;
typedef pair<LL,LL> vec;
const int maxn=100000;

int n,C,D;LL f[maxn+5],ans;
struct data {int D,P,R,G;} a[maxn+5];
int m,top;vec tem[maxn+5],stk[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline bool cmp(const data &a,const data &b) {return a.D<b.D;}
inline vec operator - (const vec &a,const vec &b) {return mp(b.X-a.X,b.Y-a.Y);}
inline DB Cross(const vec &a,const vec &b) {return (DB)a.X*b.Y-(DB)a.Y*b.X;}
#define F(i) (f[i]-(LL)a[i].G*a[i].D+a[i].R-a[i].G)
void Solve(int L,int R){
    if (L==R) return; int mid=L+(R-L>>1);
    Solve(L,mid);
    m=0;for (int i=L;i<=mid;i++) if (f[i]>=0) tem[++m]=mp(a[i].G,F(i));
    sort(tem+1,tem+m+1);top=0;
    for (int i=1,j;i<=m;i=j+1){
        for (j=i;j<=m && tem[i].X==tem[j].X;j++);j--;
        while (top>1 && Cross(stk[top]-stk[top-1],tem[j]-stk[top-1])>=0) top--;
        stk[++top]=tem[j];
    }
    if (!top) {Solve(mid+1,R);return;}
    for (int i=mid+1;i<=R;i++){
        int l=1,r=top-1;
        for (int mid=l+(r-l>>1);l<=r;mid=l+(r-l>>1))
            stk[mid+1].Y-stk[mid].Y<=(stk[mid+1].X-stk[mid].X)*(-a[i].D)?r=mid-1:l=mid+1;
        f[i]=max(f[i],stk[l].Y+stk[l].X*a[i].D-a[i].P);
    }
    Solve(mid+1,R);
}
int main(){
    freopen("3842.in","r",stdin);freopen("3842.out","w",stdout);
    for (int te=1;readi(n),readi(C),readi(D),n || C || D;te++){
        for (int i=1;i<=n;i++) readi(a[i].D),readi(a[i].P),readi(a[i].R),readi(a[i].G);
        sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++) f[i]=C-a[i].P;Solve(1,n);
        ans=C;for (int i=1;i<=n;i++) if (f[i]>=0) ans=max(ans,f[i]+(LL)a[i].G*(D-a[i].D)+a[i].R);
        printf("Case %d: %lld\n",te,ans);
    }
    return 0;
}