9-4日互测T2 factory

一道非常好的斜率DP练习题from Z博士。

题面

(因为我懒所以我吃了latex,原题是有latex的)

【问题描述】

在遥远的新日暮里, 哲 ♂ 学家们正在潜心研究健美, 他们向工厂送去了 n 个订单, 要求工厂按顺序生产健美器材. 由于工厂只有一台机器, 等工厂开 始处理订单时, 订单已经全部过期了 QAQ. 工厂的机器每次启动时需要 T 的 时间, 而工厂每生产一批产品就需要关闭机器, 然后将这批产品送往新日暮里 (可视为瞬间送到). 每个产品生产所需时间为 t i , 每个订单的违约金为 x i , 同 时产品生产出来后每单位时间需要花费 w i 的费用储存。 对于每一批产品, 所需要支付的费用是完成这批产品的时间 这批产品 的总违约金 + 每个产品生产出来后等待送往新日暮里的时间 储存的费用. 你可以随意分批生产产品, 注意要按顺序生产产品. 老板并不想欠下 3.5 个亿, 更不想接受哲学的拷 ♂ 问. 他向你询问最小需要支付的费用是多少?

【输入格式】

从 factory.in 中读入数据。 输入文件第一行包括两个正整数 n, T , 分别表示订单的数量和机器启动 的时间。 接下来 n 行每行三个数 t i , x i , w i , 描述一个订单, 分别表示生产所需的时 间, 违约金和储存所需的费用。

【输出格式】

输出到文件 factory.out 中。 输出包括一个整数,表示最小需要支付的费用。

题解

fif_i表示从生产第ii~nn个产品所需要的最小费用。 根据题意可以得到DP方程:

fi=minj=in(fj+1+T(k=inxk)+k=1jl=ijxltk+k=ijl=k+1jwktl)f_i=\min_{j=i}^n(f_{j+1}+T(\sum_{k=i}^nx_k)+\sum_{k=1}^{j}\sum_{l=i}^jx_lt_k+\sum_{k=i}^{j}\sum_{l=k+1}^{j} w_k t_l)

然后可以提取出T(k=inxk)T(\sum_{k=i}^nx_k)得到:

fi=T(k=inxk)+minj=in(fj+1+k=1jl=ijxltk+k=ijl=k+1jwktl)f_i=T(\sum_{k=i}^nx_k)+\min_{j=i}^n(f_{j+1}+\sum_{k=1}^{j}\sum_{l=i}^jx_lt_k+\sum_{k=i}^{j}\sum_{l=k+1}^{j}w_kt_l)

接着我们发现 i=1nj=1uxitj\sum_{i=1}^{n}\sum_{j=1}^{u}x_it_j 是一定会进入答案的,则我们可以在转移方程里面去掉这一部分,然后发现可以做一次提公因式并把方程简化为:

fi=T(k=inxk)+minj=in(fj+1+k=ij((xk+wk)l=k+1jtl))f_i=T(\sum_{k=i}^nx_k)+\min_{j=i}^n(f_{j+1}+ \sum_{k=i}^j((x_k+w_k) \sum_{l=k+1}^{j}t_l))

并且最后的结果为

f1+i=1nj=1uxitjf_1+\sum_{i=1}^{n}\sum_{j=1}^{u}x_it_j

可是,,,这还是 O(n4)O(n^4) 的啊。。。 但我们可以用后缀和优化一波。 计算x,w,tx,w,t的后缀和X,W,TX,W,T,以及zi=(xi+wi)(Ti+1)z_i=(x_i+w_i)(T_{i+1})的后缀和ZZ 则方程就会瞬间变为:

fi=TXk+minj=in(fj+1+ZiZj+1(Xi+WiXj+1Wj+1)Tj+1)f_i=TX_k+min^n_{j=i}(f_{j+1}+Z_i-Z_{j+1}-(X_i+W_i-X_{j+1}-W_{j+1})T_{j+1})

这就是O(n2)O(n^2)的方程了。 然后发现可以斜率优化!!! 一波O(n)O(n)妥妥AC。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: factory.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef unsigned long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll n,yT;
ll t[555555],x[555555],w[555555],z[555555],T[555555],X[555555],W[555555],Z[555555],f[555555];
#define x(a) (f[a]-Z[a]+(X[a]+W[a])*T[a])
#define y(a) T[a]
#define fst q[l]
#define ffst q[l+1]
#define lst q[r]
#define llst q[r-1]
#define nxt q[++r]
ll q[555555],l,r;
int main(){
freopen("factory.in","r",stdin);
freopen("factory.out","w",stdout);
ll n,yT,ans=0;
scanf("%llu%llu",&n,&yT);

for(ll i=1;i<=n;++i){
scanf("%llu%llu%llu",t+i,x+i,w+i);
}
for(ll i=1;i<=n;++i){
T[i]=T[i-1]+t[i];
}
for(ll i=1;i<=n;++i)ans+=x[i]*T[i];
for(ll i=n;i>=1;--i){
z[i]=(x[i]+w[i])*(T[i+1]);
X[i]=x[i]+X[i+1];
W[i]=w[i]+W[i+1];
Z[i]=z[i]+Z[i+1];
T[i]=t[i]+T[i+1];
}
l=1;r=0;
nxt=n+1;
for(ll i=n;i>=1;--i){
while(l<r&&(x(ffst)-x(fst))*1./(y(ffst)-y(fst))-(X[i]+W[i])<=eps)++l;
ll j=q[l];
// debug("%llu ",j);
f[i]=X[i]*yT+f[j]+Z[i]-Z[j]-(X[i]+W[i]-X[j]-W[j])*T[j];
while(l<r&&(x(i)-x(lst))*1./(y(i)-y(lst))-(x(i)-x(llst))*1./(y(i)-y(llst))<=eps)--r;
nxt=i;
// debug("%llu\n",f[i]);
}
// for(ll i=1;i<=n+1;++i)printf("%llu %llu %llu %llu %llu %llu %llu\n",x(i),y(i),f[i],Z[i],X[i],W[i],T[i]);
ans+=f[1];
printf("%llu\n",ans);
return 0;
}

文章目录
  1. 1. 题面
    1. 1.1. 【问题描述】
    2. 1.2. 【输入格式】
    3. 1.3. 【输出格式】
  2. 2. 题解
|

博客使用Disqus作为评论系统