由于这三道题都是同一道题，只是数据范围不同，故拉成同一篇博客
题意
有$n$个任务，机器人($jxc$)会把这$n$个任务分成若干批，从时刻$0$开始，任务将被分批加工，执行第$i$个任务需要花费时间为$T_i$。另外，在每一批任务开始前，机器需要$S$的启动时间。
同一批任务将在同一时刻完成。每个任务的费用$=$它完成的时间$\times$一个费用的系数$C_i$。
思路
对于$n \leq 5000$的数据
时间复杂度$O(N^2)$
设$f[i]$表示前$i$个任务所花费最小价值。
初始化：
$$f[i]=inf|1<=i<=n,f[0]=0$$
转移方程：
$$f[i]=min \left{f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right}$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
int n,S,f[5010],t[5010],c[5010];
int main(){
cin>>n>>S;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
t[i]=t[i-1]+x;
c[i]=c[i-1]+y;
}
memset(f,63,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i]=min(f[j-1]+S*(c[n]-c[j-1])+t[i]*(c[i]-c[j-1]),f[i]);
}
}
cout<<f[n]<<endl;
return 0;
}
|
对于$1\leq N \leq 10^4$的数据
时间复杂度约为$O(N)$
转移方程同上，
$$f[i]=min \left{ f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right }$$
将只含有$i$的项移出，得：
$$f[i]=min \left { f[j-1]-Sc[j-1]-t[i]c[j-1]|1<=j<=i \right }+Sc[n]+t[i]c[i]$$
合并同类项，得：
$$f[i]=min \left { f[j]-(S+t[i])c[j]|0<=j<=i-1 \right }+Sc[n]+t[i]*c[i]$$
设$y=f[j]$,$k=S+t[i]$,$x=c[j]$,$b=Sc[n]+t[i]c[i]$
那么：
$$f[i]=y-kx+b$$
即：
$$y=kx+(f[i]-b)$$
斜率优化一：
因为$t[i]$在递增，斜率$k$在变大，直线越来越陡，所以队首的两个点之间斜率至少要大于$(S+t[i])$。
即：$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])>(S+t[i])$
即：若$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])<=(S+t[i])$，队首弹出
化简，得：若$(f[q[l+1]]-f[q[l]])<=(S+t[i])*(c[q[l+1]]-c[q[l]])$，队首弹出
斜率优化二：
确保右侧的斜率大于左侧的斜率，即：$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])<(f[i]-f[q[r]])/(c[i]-c[q[r]])$。
若$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])>=(f[i]-f[q[r]])/(c[i]-c[q[r]])$,队尾弹出。
化简，得：若$(f[i]-f[q[r]])(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])(c[i]-c[q[r]])$，队尾弹出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
int n,S,f[300010],t[300010],c[300010],q[300010],l,r;
int main(){
cin>>n>>S;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
t[i]=t[i-1]+x;
c[i]=c[i-1]+y;
}
memset(f,63,sizeof(f));
f[0]=0;
l=1,r=1;
for(int i=1;i<=n;i++){
int k=S+t[i];
while(l<r&&f[q[l+1]]-f[q[l]]<=k*(c[q[l+1]]-c[q[l]])) l++;
f[i]=f[q[l]]-k*c[q[l]]+t[i]*c[i]+S*c[n];
while(l<r&&(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])) r--;
q[++r]=i;
}
cout<<f[n]<<endl;
return 0;
}
|
对于$1 \leq N \leq 3 \times 10^5 , \left| T_i \right|<2^8$的数据
虽然添加了单调队列的优化，但是时间可以为负数，所以之前维护的单调性就不存在了，所以我们需要使用二分+单调队列来维护斜率。
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
| #include<bits/stdc++.h>
using namespace std;
long long n,S,f[300010],t[300010],c[300010],q[300010],l,r,L,R;
long long Cut(long long j){return f[j]-c[n]*t[j]+c[j]*t[j]-c[j]*S;}
int main(){
cin>>n>>S;
for(long long i=1;i<=n;i++){
long long x,y;
cin>>x>>y;
t[i]=t[i-1]+x;
c[i]=c[i-1]+y;
}
memset(f,127,sizeof(f));
f[0]=0;
L=0,R=0;
for(long long i=1;i<=n;i++){
l=0,r=R-1;long long ans=R;
while(l<=r){
long long mid=(l+r)>>1;
if((c[q[mid+1]]-c[q[mid]])*t[i]<=Cut(q[mid+1])-Cut(q[mid])) ans=mid,r=mid-1;
else l=mid+1;
}
long long j=q[ans];
f[i]=f[j]+(c[n]-c[j])*(t[i]-t[j]+S);
while(L<R&&(Cut(q[R])-Cut(q[R-1]))*(c[i]-c[q[R]])>=(Cut(i)-Cut(q[R]))*(c[q[R]]-c[q[R-1]])) R--;
q[++R]=i;
}
cout<<f[n]<<endl;
return 0;
}
|