BZOJ 2726 任务安排

发表于 | 更新于

又被克了很长时间 官方数据有误？

Link

Solution

DP方程为 f(i)=min{f(j−1)+[S+cT(j,i)]×cF(j,n)∣j<=i}f(i)=min\{f(j-1)+[S+cT(j,i)]\times cF(j,n) | j<=i\} cT,cFcT,cF分别表示相应量的区间和 j<kj<k且jj优于kk当且仅当 [f(j−1)+(S−Tj−1)(Fn−Fj−1)]−[fk−1+(S−Tk−1)(Fn−Fk−1)]Fj−1−Fk−1>Ti\dfrac {[f(j-1)+(S-T_{j-1})(F_n-F_{j-1})]-[f_{k-1}+(S-T_{k-1})(F_n-F_{k-1})]}{F_{j-1}-F_{k-1}}>T_i T,FT,F表示相应量的前缀和 一开始没变号。。抓瞎了。。 如果TiT_i递增的话，就可以单调队列维护一个下凸壳。 TiT_i不递增，没办法，只能CDQ或者平衡树。 CDQ做法： 分治之前按照TiT_i排序，分治的每层把前半部分挑出来分治下去，回溯的时候按照idid的大小merge。 然后就可以单调队列了。

Tips

判上下凸最好用叉积，就不用讨论x为0之类的。 比较斜率与一个数最好讨论xx的符号，通过移项，相应变号，避免除法。 因为这个WA了很长时间。 还有，第一次编译一定要-Wall！！ （Windows需要alias可以用doskey实现）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//Code by Lucida
#include<bits/stdc++.h>
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
template <class T> inline void red(T &x)
{
	static int f,ch;
	f=1;
	while(!isdigit(ch=getchar()))
		if(ch=='-') f=-1;
	x=ch-'0';
	while(isdigit(ch=getchar()))
		(x*=10)+=ch-'0';
	x*=f;
}
typedef long long LL;
typedef long long ld;
using std::merge;
using std::sort;
using std::copy;

const int MAXN=300000+10;
LL f[MAXN],cx[MAXN],cy[MAXN];
LL F[MAXN],T[MAXN],n,S;

struct point
{
	LL x,y;int id;
	point(){}
	point(LL _x,LL _y,int _id=0):x(_x),y(_y),id(_id){}
};
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);}
bool operator <=(point a,LL b)
{
	return a.x>0?a.y-(ld)a.x*b<=0:
				 a.y-(ld)a.x*b>=0;
}
ld outer(point a,point b){return (ld)a.x*b.y-(ld)a.y*b.x;}
struct Opt
{
	int id;LL T;
	bool operator <(Opt a){return id<a.id;}
}p[MAXN],t[MAXN];
bool cmpT(Opt a,Opt b){return a.T<b.T;}
void partition(int l,int r,int midv)
{
	int pl=l,pr=(l+r)/2+1;
	for(int i=l;i<=r;i++)
		if(p[i].id<=midv) t[pl++]=p[i];
		else t[pr++]=p[i];
	copy(t+l,t+r+1,p+l);
}
void DC(int l,int r)
{
	static point Q[MAXN];
	int head,tail;
	if(l==r)
	{
		int i=l,j=l;
		chkmn(f[i],f[j-1]+cy[j]+T[i]*(F[n]-F[j-1]));
		return;
	}
	int mid=(l+r)/2;
	partition(l,r,mid);
	DC(l,mid);
	head=1,tail=0;
	#define count(a,b) (b-a+1)
	for(int pl=l;pl<=mid;pl++)
	{
		point cur=point(cx[pl],f[pl-1]+cy[pl],pl);
		while(count(head,tail)>=2 && outer(cur-Q[tail-1],Q[tail]-Q[tail-1])>=0)//(cur-Q[tail])<=(Q[tail]-Q[tail-1]))
			tail--;
		Q[++tail]=cur;
	}
	for(int pr=mid+1;pr<=r;pr++)
	{
		if(pr<r) assert(p[pr].T<=p[pr+1].T);
		while(count(head,tail)>=2 && (Q[head]-Q[head+1])<=p[pr].T) 
			head++;
		int i=p[pr].id,j=Q[head].id;
		chkmn(f[i],f[j-1]+cy[j]+T[i]*(F[n]-F[j-1]));
	}
	#undef count
	DC(mid+1,r);
	merge(p+l,p+mid+1,p+mid+1,p+r+1,t+l);
	copy(t+l,t+r+1,p+l);
}
void solve()
{
	cx[0]=cy[0]=0;
	for(int i=1;i<=n;i++)
		p[i].id=i,p[i].T=T[i];
	
	memset(f,127,sizeof(f));f[0]=0;
	sort(p+1,p+1+n,cmpT);DC(1,n);
	printf("%lld\n",f[n]);
}
int main()
{
	freopen("input","r",stdin);
	red(n),red(S);
	for(int i=1;i<=n;i++)
	{
		red(T[i]),red(F[i]);
		T[i]+=T[i-1],F[i]+=F[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		cy[i]=(LL)(S-T[i-1])*(F[n]-F[i-1]);
		cx[i]=F[i-1];
	}
	solve();	
	return 0;
}