BZOJ 2424: [HAOI2010]订货

2424: [HAOI2010]订货

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 915 Solved: 639
[Submit][Status][Discuss]

Description

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

Input

第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

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

Sample Input

3 1 1000
2 4 8
1 2 4

Sample Output

HINT

Source

Day1

[Submit][Status][Discuss]

动态规划。

一开始看到题面的时候以为是那道经典的贪心问题，就是维护当前最优单价，不断转移。

然而这道题限制了仓库的容量，使得最优单价不能直接向后转移，所以需要动态规划。

设$f[i][j]$表示经过了第$i$个月（此时已经到了月底），仓库中剩余量为$j$的当前最小费用。

转移如下：

$f[i][j+1]=min(f[i][j+1],f[i][j]+D_{i})$ 表示可以在本月额外购进一单位作为储存。

当$j geq U_{i+1}$， $f[i+1][j-U_{i+1}]=min(f[i+1][j-U_{i+1}],f[i][j]+M*j$ 表示如果当前储备够下个月出售，下个月可以不购进商品，只需支付两个月之间的储存费用。

当$j lt U_{i+1}$， $f[i+1][0]=min(f[i+1][0],f[i][j]+M*j+(U_{i+1}-j)*D_{i+1}$ 表示如果当前储备不够下个月，下个月除了需要支付储存费用，还需要额外购进一些商品。

 1 #include <cstdio>
 2 
 3 inline int nextChar(void)
 4 {
 5     const static int siz = 1024;
 6     
 7     static char buf[siz];
 8     static char *hd = buf + siz;
 9     static char *tl = buf + siz;
10     
11     if (hd == tl)
12         fread(hd = buf, 1, siz, stdin);
13         
14     return *hd++;
15 }
16 
17 inline int nextInt(void)
18 {
19     register int ret = 0;
20     register int neg = false;
21     register int bit = nextChar();
22     
23     for (; bit < 48; bit = nextChar())
24         if (bit == '-')neg ^= true;
25         
26     for (; bit > 47; bit = nextChar())
27         ret = ret * 10 + bit - 48;
28         
29     return neg ? -ret : ret;
30 }
31 
32 const int inf = 1e9;
33 const int maxn = 55;
34 const int maxm = 10005;
35 
36 int N, M, S;
37 int U[maxn];
38 int D[maxn];
39 
40 int f[maxn][maxm];
41 
42 inline void Min(int &a, const int &b)
43 {
44     if (a > b)a = b;
45 }
46 
47 signed main(void)
48 {
49     N = nextInt();
50     M = nextInt();
51     S = nextInt();
52     
53     for (int i = 1; i <= N; ++i)
54         U[i] = nextInt();
55         
56     for (int i = 1; i <= N; ++i)
57         D[i] = nextInt();
58         
59     for (int i = 0; i <= N; ++i)
60         for (int j = 0; j <= S; ++j)
61             f[i][j] = inf;
62             
63     f[1][0] = D[1] * U[1];
64     
65     for (int i = 0; i <= N; ++i)
66         for (int j = 0; j <= S; ++j)
67             if (f[i][j] < inf)
68             {
69                 Min(f[i][j + 1], f[i][j] + D[i]);
70                 if (j >= U[i + 1])
71                     Min(f[i + 1][j - U[i + 1]], f[i][j] + j * M);
72                 else
73                     Min(f[i + 1][0], f[i][j] + (U[i + 1] - j) * D[i + 1] + j * M);
74             }
75             
76     int ans = inf;
77     
78     for (int i = 0; i <= S; ++i)
79         Min(ans, f[N][i]);
80         
81     printf("%d
", ans);
82 }
83

突然，机房小伙伴们惊奇地看我：“这特么不是裸的费用流吗？”

WOC，我是有多蠢，去想DP？LTY神犇要来HACK我了，好怕怕~~~

补上最小费用流代码……

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 inline char nextChar(void)
  5 {
  6     static const int siz = 1024;
  7     
  8     static char buf[siz];
  9     static char *hd = buf + siz;
 10     static char *tl = buf + siz;
 11     
 12     if (hd == tl)
 13         fread(hd = buf, 1, siz, stdin);
 14     
 15     return *hd++;
 16 }
 17 
 18 inline int nextInt(void)
 19 {
 20     register int ret = 0;
 21     register int neg = false;
 22     register int bit = nextChar();
 23     
 24     for (; bit < 48; bit = nextChar())
 25         if (bit == '-')neg ^= true;
 26     
 27     for (; bit > 47; bit = nextChar())
 28         ret = ret * 10 + bit - 48;
 29         
 30     return neg ? -ret : ret;
 31 }
 32 
 33 const int siz = 50005;
 34 const int inf = 1000000007;
 35 
 36 int tot;
 37 int s, t;
 38 int hd[siz];
 39 int to[siz];
 40 int fl[siz];
 41 int vl[siz];
 42 int nt[siz];
 43 
 44 inline void add(int u, int v, int f, int w)
 45 {
 46     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; vl[tot] = +w; hd[u] = tot++;
 47     nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; vl[tot] = -w; hd[v] = tot++;
 48 }
 49 
 50 int dis[siz];
 51 int pre[siz];
 52 
 53 inline bool spfa(void)
 54 {
 55     static int que[siz];
 56     static int inq[siz];
 57     static int head, tail;
 58     
 59     memset(dis, 0x3f, sizeof(dis));
 60     memset(inq, 0, sizeof(inq));
 61     head = 0, tail = 0;
 62     que[tail++] = s;
 63     pre[s] = -1;
 64     dis[s] = 0;
 65     inq[s] = 1;
 66     
 67     while (head != tail)
 68     {
 69         int u = que[head++], v; inq[u] = 0;
 70         
 71         for (int i = hd[u]; ~i; i = nt[i])
 72             if (dis[v = to[i]] > dis[u] + vl[i] && fl[i])
 73             {
 74                 dis[v] = dis[u] + vl[i], pre[v] = i ^ 1;
 75                 if (!inq[v])inq[que[tail++] = v] = 1;
 76             }
 77     }
 78     
 79     return dis[t] < 0x3f3f3f3f;
 80 }
 81 
 82 inline int minCost(void)
 83 {
 84     int cost = 0, flow;
 85     
 86     while (spfa())
 87     {
 88         flow = inf;
 89         
 90         for (int i = pre[t]; ~i; i = pre[to[i]])
 91             if (flow > fl[i ^ 1])flow = fl[i ^ 1];
 92         
 93         for (int i = pre[t]; ~i; i = pre[to[i]])
 94             fl[i] += flow, fl[i ^ 1] -= flow;
 95             
 96         cost += dis[t] * flow;
 97     }
 98     
 99     return cost;
100 }
101 
102 int n, m, k;
103 
104 signed main(void)
105 {
106     n = nextInt();
107     m = nextInt();
108     k = nextInt();
109     
110     s = 0, t = n + 1;
111     
112     memset(hd, -1, sizeof(hd));
113     
114     for (int i = 1; i <= n; ++i)
115         add(i, t, nextInt(), 0);
116         
117     for (int i = 1; i <= n; ++i)
118         add(s, i, inf, nextInt());
119         
120     for (int i = 1; i < n; ++i)
121         add(i, i + 1, k, m);
122         
123     printf("%d
", minCost());
124 }

@Author: YouSiki