menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP]BZOJ2424(HAOI2010)【订货】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

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

解题报告

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

$$ \begin{align} 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{align} $$

记下前缀最小值就行了。

示例程序

#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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up