首页 > 代码库 > 【HAOI2010】订货

【HAOI2010】订货

可以DP也可以是费用流,然而被我用非常简单的DP破了【开心】

原题:

某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。

0<=n<=50,0<=m<=10,0<=S<=10000,0<=Ui<=10000,0<=di<=100

 

恩紫萱的讲解说要用队列优化DP,我太弱没看懂,自己想出了一个我觉得比较妙的方法DP掉了

核心思路是在买东西的时候f[i]只与f[i-1]的最优值有关(注意是最优值)

然后要买的时候从1到S顺推,f[i]=min(f[i],f[i-1]+d[i])

恩原理我也不是很好解释,直接丢个图吧

技术分享

可以理解为f[i-1]代表了1到i-1所有的方案,但是都没有f[i]优,再往上考虑的话,由于增加的费用都是一样的,所以和f[1]到f[i-1]有关的方案不会优于f[i]相关的方案,就只考虑f[i]了

如果f[i]不是更优,f[i-1]代表了f[1]到f[i-1]的方案,只管使用即可

然后还有许多需要注意的细节(我就是因为细节问题拖了很久才A quq)

首先货物是可以进货不入库直接卖,不占用仓库空间,所以实际上仓库有M+a[i]的储存空间(每个月的需求也可能超过仓库容量),然后每个月结束的时候f中1到M不用处理,下个月直接转移即可,但是M+1到M+a[i]这一段一定要处理成正无穷,不然会影响到下个月(我就是因为这个细节卡了一下午,差点弃疗quq)

还有更多的细节问题,大家自己体验吧一。一

DP代码非常短

费用流的代码以后补上

代码(DP):

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int read(){int z=0,mark=1;  char ch=getchar();
 8     while(ch<0||ch>9){if(ch==-)mark=-1;  ch=getchar();}
 9     while(ch>=0&&ch<=9){z=(z<<3)+(z<<1)+ch-0;  ch=getchar();}
10     return z*mark;
11 }
12 const int oo=168430090;
13 int n,m,ns;  int a[110],b[110];
14 int f[21000];
15 int main(){//freopen("ddd.in","r",stdin);
16     memset(f,10,sizeof(f));
17     cin>>n>>ns>>m;
18     for(int i=1;i<=n;i++)  a[i]=read();
19     for(int i=1;i<=n;i++)  b[i]=read();
20     f[0]=0;  a[0]=0;
21     for(int i=1;i<=n;i++){
22         for(int j=0;j<=m;j++)  f[j]=f[j+a[i-1]]+j*ns;
23         for(int j=m+1;j<=m+a[i-1];j++)  f[j]=oo;
24         for(int j=1;j<=m+a[i];j++)  f[j]=min(f[j],f[j-1]+b[i]);
25     }
26     cout<<f[a[n]]<<endl;
27     return 0;
28 }
View Code

 

【HAOI2010】订货