首页 > 代码库 > 订货(bzoj 2424)

订货(bzoj 2424)

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

34
#include<cstdio>
#include<iostream>
/*
  状态很好定义:f[i][j]表示到第i个月底,存货为j的最小花费。
  转移方程:f[i][j]=min{f[i-1][k]+k*m+(u[i]+j-k)*w[i]}(k≤u[i]+j)
                  =min{f[i-1][k]+k*(m-w[i])}+(u[i]+j)*w[i](k≤u[i]+j)
  因为在枚举j时,k的取值范围也是不断增大的,所以可以用以前的来更新现在的。
*/
#include<cstring>
#define N 60
#define M 10010
using namespace std;
int n,m,S,u[N],d[N],f[N][M];
int main(){
    scanf("%d%d%d",&n,&m,&S);
    for(int i=1;i<=n;i++)scanf("%d",&u[i]);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    for(int i=1;i<=S;i++)f[0][i]=1e9;
    for(int i=1;i<=n;i++){
        int res=1e9,k=0;
        for(int j=0;j<=S;j++){
            while(k<=min(u[i]+j,S)){res=min(res,f[i-1][k]+k*(m-d[i]));k++;}
            f[i][j]=res+(u[i]+j)*d[i];
        }
    }
    printf("%d",f[n][0]);
    return 0;

 

订货(bzoj 2424)