BZOJ 2424: [HAOI2010]订货

2023-01-06 13:54:15

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}$ 表示如果当前储备不够下个月，下个月除了需要支付储存费用，还需要额外购进一些商品。

 #include <cstdio>

 inline int nextChar(void)

 {

     const static int siz = ;

     static char buf[siz];

     static char *hd = buf + siz;

     static char *tl = buf + siz;

     if (hd == tl)

         fread(hd = buf, , siz, stdin);

     return *hd++;

 }

 inline int nextInt(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = nextChar();

     for (; bit < ; bit = nextChar())

         if (bit == '-')neg ^= true;

     for (; bit > ; bit = nextChar())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 const int inf = 1e9;

 const int maxn = ;

 const int maxm = ;

 int N, M, S;

 int U[maxn];

 int D[maxn];

 int f[maxn][maxm];

 inline void Min(int &a, const int &b)

 {

     if (a > b)a = b;

 }

 signed main(void)

 {

     N = nextInt();

     M = nextInt();

     S = nextInt();

     for (int i = ; i <= N; ++i)

         U[i] = nextInt();

     for (int i = ; i <= N; ++i)

         D[i] = nextInt();

     for (int i = ; i <= N; ++i)

         for (int j = ; j <= S; ++j)

             f[i][j] = inf;

     f[][] = D[] * U[];

     for (int i = ; i <= N; ++i)

         for (int j = ; j <= S; ++j)

             if (f[i][j] < inf)

             {

                 Min(f[i][j + ], f[i][j] + D[i]);

                 if (j >= U[i + ])

                     Min(f[i + ][j - U[i + ]], f[i][j] + j * M);

                 else

                     Min(f[i + ][], f[i][j] + (U[i + ] - j) * D[i + ] + j * M);

             }

     int ans = inf;

     for (int i = ; i <= S; ++i)

         Min(ans, f[N][i]);

     printf("%d\n", ans);

 }

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

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

补上最小费用流代码……

 #include <cstdio>

 #include <cstring>

 inline char nextChar(void)

 {

     static const int siz = ;

     static char buf[siz];

     static char *hd = buf + siz;

     static char *tl = buf + siz;

     if (hd == tl)

         fread(hd = buf, , siz, stdin);

     return *hd++;

 }

 inline int nextInt(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = nextChar();

     for (; bit < ; bit = nextChar())

         if (bit == '-')neg ^= true;

     for (; bit > ; bit = nextChar())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 const int siz = ;

 const int inf = ;

 int tot;

 int s, t;

 int hd[siz];

 int to[siz];

 int fl[siz];

 int vl[siz];

 int nt[siz];

 inline void add(int u, int v, int f, int w)

 {

     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; vl[tot] = +w; hd[u] = tot++;

     nt[tot] = hd[v]; to[tot] = u; fl[tot] = ; vl[tot] = -w; hd[v] = tot++;

 }

 int dis[siz];

 int pre[siz];

 inline bool spfa(void)

 {

     static int que[siz];

     static int inq[siz];

     static int head, tail;

     memset(dis, 0x3f, sizeof(dis));

     memset(inq, , sizeof(inq));

     head = , tail = ;

     que[tail++] = s;

     pre[s] = -;

     dis[s] = ;

     inq[s] = ;

     while (head != tail)

     {

         int u = que[head++], v; inq[u] = ;

         for (int i = hd[u]; ~i; i = nt[i])

             if (dis[v = to[i]] > dis[u] + vl[i] && fl[i])

             {

                 dis[v] = dis[u] + vl[i], pre[v] = i ^ ;

                 if (!inq[v])inq[que[tail++] = v] = ;

             }

     }

     return dis[t] < 0x3f3f3f3f;

 }

 inline int minCost(void)

 {

     int cost = , flow;

     while (spfa())

     {

         flow = inf;

         for (int i = pre[t]; ~i; i = pre[to[i]])

             if (flow > fl[i ^ ])flow = fl[i ^ ];

         for (int i = pre[t]; ~i; i = pre[to[i]])

             fl[i] += flow, fl[i ^ ] -= flow;

         cost += dis[t] * flow;

     }

     return cost;

 }

 int n, m, k;

 signed main(void)

 {

     n = nextInt();

     m = nextInt();

     k = nextInt();

     s = , t = n + ;

     memset(hd, -, sizeof(hd));

     for (int i = ; i <= n; ++i)

         add(i, t, nextInt(), );

     for (int i = ; i <= n; ++i)

         add(s, i, inf, nextInt());

     for (int i = ; i < n; ++i)

         add(i, i + , k, m);

     printf("%d\n", minCost());

 }

@Author: YouSiki

码农公寓