HAOI 2010 订货

JZYZOJ 1327 订货

luogu P2517 订货

首先呢，看到有人说这是网络流。好吧我不会。
所以我就用常规点的方法来写吧。

很显然\(DP\)，不要问我为什么，这就跟证明贪心一样。

1. 闭上眼睛
2. 想一想
3. WA是对的

好了不多哔哔直接开始。

首先我们的货物不一定只能小于等于\(s\)，我们进货后可以直接卖掉不进仓库

我们要求的是最小的成本，所以\(f[j]\)肯定就是存成本了。

呢么\(j\)是什么意思呢。\(j\)表示当前仓库里有多少货物。

但是你会发现没有时间对吧我们用\(i\)来表示时间

所以\(f[j]\)就表示在\(i\)月时仓库里有\(j\)个货物所需成本。

现在假设我们已知\(i-1\)月的$f[j]

并且\(i-1\)月需求量\(u[i-1]\)也是已知的

到了这个月因为有储存费所以成本会增加

所以在第\(i\)月还未进货时的成本为

f[j] = f[j+u[i-1]] + j*m;

当然仓库也是有大小的超过\(s\)的是不合法的所以在求最优解之前

for(register int j = s+1;j <= s+u[i-1];j++) f[j] = INF;

呢么\(i\)月的\(f[j]\)的最优值我们就可以求得

f[j] = min(f[j],f[j-1]+d[i];

所以我们只要从第\(1\)月一直求到第\(n\)月就好了

#include <bits/stdc++.h>
using namespace std;


const int N = 105,S = 20005,INF = 0x7f7f7f7f;
int n,m,s,u[N] = {},d[N] = {},f[S] = {};


inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<3)+(x<<1) + ch-'0';
        ch = getchar();
    }
    return x;
}


int main()
{
    n = read(); m = read(); s = read();
    for(register int i = 1;i <= n;i++) u[i] = read();
    for(register int i = 1;i <= n;i++) d[i] = read();
    memset(f,INF,sizeof(f));
    u[0] = f[0] = 0;
    for(register int i = 1;i <= n;i++)
    {
        for(register int j = 0;j <= s;j++) f[j] = f[j+u[i-1]] + j*m;
        for(register int j = s+1;j <= s+u[i-1];j++) f[j] = INF;
        for(register int j = 1;j <= s+u[i];j++) f[j] = min(f[j],f[j-1]+d[i]);
    }
    printf("%d\n",f[u[n]]);
    return 0;
}

HAOI 2010 订货

原文：https://www.cnblogs.com/Mark-X/p/11699564.html