某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。
只有1行，一个整数，代表最低成本
动态规划。
一开始看到题面的时候以为是那道经典的贪心问题，就是维护当前最优单价，不断转移。
然而这道题限制了仓库的容量，使得最优单价不能直接向后转移，所以需要动态规划。
设$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\n", ans); 82 } 83
@Author: YouSiki
原文：http://www.cnblogs.com/yousiki/p/6254933.html