【bzoj2424】HAOI2010订货

描述 Description

某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。

输入格式 Input Format

第1行:n,m,S (0<=n<=50,0<=m<=10,0<=S<=10000)

第2行:U1,U2,…,Ui,…,Un (0<=Ui<=10000)

第3行:d1,d2,…,di,…,dn (0<=di<=100)

输出格式 Output Format

只有1行,一个整数,代表最低成本

样例输入 Sample Input

3 1 1000

2 4 8

1 2 4

样例输出 Sample Output

34

题解 Solution

用$f[i][j]$表示在第$i$个月存货量为$j$的最小花费,得到

$f[i][j]=min{f[i−1][k]+(u[i]+j−k)∗d[i]+m∗k}(0≤j≤s,k≤u[i]+j)$

变形后:$f[i][j]=min{f[i−1][k]+(m−d[i])∗k}+(u[i]+j)∗d[i]$

那么对于阶段$i$状态$j$,考虑$i-1$的决策$x$ , $y$ , $x<y$,如果$x$更优,则有

$f[i−1][x]+(m−d[i])∗x≤f[i−1][y]+(m−d[i])∗y$

对于每个i我们维护一个队列q,并且从S到0枚举j,从上一阶段队头取最优值,并与队尾比较即可。

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
#include<bits/stdc++.h>
using namespace std;
int u[60];
int lmt;
int d[60];
int n,m;
int q[60][10010];
int head[60];
int tail[60];
int f[60][10010];

void solution() {
for (int i = 1; i <= n; i++)
head[i] = 1, tail[i] = 0;
for (int i = 1; i <= n; i++) {
for (int j = lmt; j >= 0; j--) {
while (head[i - 1] < tail[i - 1] && q[i - 1][head[i - 1]] > u[i] + j)
++head[i-1];
int k = q[i - 1][head[i - 1]];
f[i][j] = f[i - 1][k] + (m - d[i]) * k + (u[i] + j) * d[i];
while (f[i][j] + (m - d[i + 1]) * j
<= f[i][q[i][tail[i]]] + (m - d[i + 1]) * q[i][tail[i]]
&& head[i] <= tail[i]) --tail[i];
q[i][++tail[i]] = j;
}
}
printf("%d\n", f[n][0]);
}

int main() {
cin >> n >> m >> lmt;
for (int i = 1; i <= n; i++)
scanf("%d", &u[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &d[i]);
solution();
return 0;
}