首页 > 代码库 > 【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 }
【HAOI2010】订货