【hdu3842】 Machine Works

时间：2023-03-09 19:34:28
【hdu3842】 Machine Works

http://acm.hdu.edu.cn/showproblem.php?pid=3842 (题目链接)

题意

　　一个公司使用一个厂房$D$天，希望获利最大。有$n$台机器，每一台可以在第$D_i$天购买，需要支付$P_i$，购买那天以后每一天可以获得$G_i$的收益，将它卖出可以获得$R_i$的收益，问到第$D+1$天的最大收益。

Solution

　　直接对天数不好dp，因为$D_i$可能会有重复，我们对机器进行dp。将时间离散化后，给机器按照$D_i$并从小到大排好序后，$f[i]$表示第$i$台机器出售那天的最大获利，那么在这一天可以卖出这段时间正在使用的机器，或者是延续上一天的状态，转移：$$f[i]=max\{f[i-1],f[j]-P[j]+R[j]+G[j]*(D[i]-D[j]-1)\}$$

　　条件是$f[j]>=P[j]$，所以：$$X[j]=G[j]$$

$$Y[j]=f[j]-P[j]+R[j]-G[j]*(D[j]+1)$$

$$K=-D[i]$$

　　所以我们CDQ一下就好了。

细节

　　多个机器的$D_i$相等，但是我们要把他们的处理顺序分开。多组数据注意清空。

代码

// hdu3842

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf (1ll<<30)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=200010;

int n,m,D,t[maxn],st[maxn],w[maxn];

LL f[maxn];

struct point {LL x,y,t;}p[maxn],np[maxn];

struct data {LL D,P,R,G,k,id;}q[maxn],nq[maxn];

bool cmp(data a,data b) {

	return a.k<b.k;

}

double slope(point a,point b) {

	return a.x==b.x ? inf*(b.y>a.y ? 1 : -1) : (double)(b.y-a.y)/(double)(b.x-a.x);

}

void solve(int l,int r) {

	if (l==r) {

		f[l]=max(f[l-1],f[l]);

		p[l]=(point){q[l].G,f[l]-q[l].P+q[l].R-q[l].G*(q[l].D+1),f[l]>=q[l].P};

		return;

	}

	int mid=(l+r)>>1,top=0,l1=l,l2=mid+1;

	for (int i=l;i<=r;i++) q[i].id<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];

	for (int i=l;i<=r;i++) q[i]=nq[i];

	solve(l,mid);

	for (int i=l;i<=mid;i++) if (p[i].t) {

			while (top>1 && slope(p[st[top-1]],p[st[top]])<slope(p[st[top]],p[i])) top--;

			st[++top]=i;

		}

	for (int i=mid+1;i<=r;i++) {

		while (top>1 && slope(p[st[top-1]],p[st[top]])<q[i].k) top--;

		int j=st[top];

		f[q[i].id]=max(f[q[i].id],p[j].y-q[i].k*p[j].x);

	}

	solve(mid+1,r);

	for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) {

		if (j>r || (i<=mid && p[i].x<p[j].x)) np[k++]=p[i++];

		else np[k++]=p[j++];

	}

	for (int i=l;i<=r;i++) p[i]=np[i];

}

int main() {

	int T=0;

	while (scanf("%d%lld%d",&n,&f[0],&D)!=EOF) {

		if (!n && !f[0] && !D) break;

		for (int i=1;i<=n;i++) {

			scanf("%lld%lld%lld%lld",&q[i].D,&q[i].P,&q[i].R,&q[i].G);

			t[i]=q[i].D;q[i].k=-q[i].D;

		}

		t[++n]=++D;q[n]=(data){D,0,0,0,-D,n};

		sort(t+1,t+1+n);m=unique(t+1,t+1+n)-t-1;

		for (int i=1;i<=n;i++) q[i].id=lower_bound(t+1,t+1+m,q[i].D)-t;

		for (int i=1;i<=n;i++) w[q[i].id]++;

		for (int i=1;i<=n;i++) w[i]+=w[i-1];

		for (int i=1;i<=n;i++) q[i].id=w[q[i].id]--;

		for (int i=1;i<=n;i++) w[i]=0;

		sort(q+1,q+1+n,cmp);

		solve(1,n);

		printf("Case %d: %lld\n",++T,f[n]);

		memset(f,0,sizeof(f));

	}

	return 0;

}

相关文章