题目概述

在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格为 $m$ ，仓库刚开始为空最后也为空，求最小价格。

解题报告

最开始写了个 $O(nS^2)​$ DP作死，然后去看题解发现是费用流不想写……就试着优化了下DP，发现竟然是水题。

$$ \begin{aligned} f[i][j]&=min\{f[i-1][k]+km+(j+w_i-k)p_i|k\le j+w_i\}\\ &=min\{f[i-1][k]+k(m-p_i)|k\le j+w_i\}+(j+w_i)p_i \end{aligned} $$

记下前缀最小值就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=50,maxs=20000;

int n,m,S,w[maxn+5],p[maxn+5];
LL f[maxn+5][maxs+5],pre[maxs+5];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&S);memset(f,63,sizeof(f));f[0][0]=0;
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);for (int i=1;i<=n;i++) scanf("%d",&p[i]);
    for (int i=1;i<=n;i++){
        pre[0]=f[i-1][0];for (int j=1;j<=S+w[i];j++) pre[j]=min(pre[j-1],f[i-1][j]+j*(m-p[i]));
        for (int j=0;j<=S;j++) f[i][j]=pre[j+w[i]]+(j+w[i])*p[i];
    }
    return printf("%lld\n",f[n][0]),0;
}