有一家生产酸奶的公司,连续n周,每周需要出货numi的单位,已经知道每一周生产单位酸奶的价格ci,并且,酸奶可以提前生产,但是存储费用是一周一单位s费用,问最少的花费。
对于要出货的酸奶,要不这一周生产,要不提前生产。
什么时候采用什么生产方式呢?
若第i周的货提前生产的话,假设在j周生产,则费用为(i-j)*s+c[j]
若c[i]>(i-j)*s+c[j],则更新c[i]=(i-j)*s+c[j]
更新要O(n^2)?
可以证明,最优的生产方式是,要不在这一周生产,要不在上一周生产(这里的上一周的c已经是更新过的)
O(n)更新数组c即可。
#include<cstdio>
#include<cstring> using namespace std; const int maxn=1e4+;
#define LL long long int c[maxn];
int num[maxn]; int main()
{
int n,s;
while(~scanf("%d%d",&n,&s))
{
for(int i=;i<=n;i++)
scanf("%d%d",&c[i],&num[i]); for(int i=;i<=n;i++)
{
if(s+c[i-]<c[i])
c[i]=s+c[i-];
}
LL ans=;
for(int i=;i<=n;i++)
{
ans+=(LL)c[i]*num[i];
}
printf("%lld\n",ans);
}
return ;
}