题解 P6769 【[USACO05MAR]Yogurt factory 奶酪工厂】

· · 题解

O(n^2) 贪心算法

思路

贪心告诉我们“只看眼下”，所以我们把 n 天分开讨论。

按照贪心的思路，对于第 i 天（1\le i\le n），其需要上交的奶酪应该全部来源于第 j 天（1\le j\le i）。

原因很简单，因为对于任意的 j（1\le j\le i），存储的每一单位奶酪到第 i（1\le i\le n）天的花费是相同的。所以，我们只需要找到一个 j，满足第 j 天存储每一单位奶酪到第 i 天的花费最少，然后第 i 天的奶酪全部来源于第 j 天，就是第 i 天上交奶酪的最小花费了。

代码实现

具体实现的方法见代码（有具体注释与代码分析）：

#include <bits/stdc++.h>
using namespace std;
int need[10001],cost[10001];
//need[i]表示第i天要上交的奶酪数
//cost[i]表示第i天买奶酪的花费
int n,S;
int main()
{
  cin>>n>>S;
  for(int i=1; i<=n; i++)
    cin>>cost[i]>>need[i];
  int Min;
  long long ans=0;//记得开longlong
  for(int i=1; i<=n; i++)//将每一天分开讨论
  {
    Min=INT_MAX;//将Min定义成最大值
    for(int j=1; j<=i; j++)//寻找最优的j
      Min=min(Min,cost[j]+S*(i-j));
    //第j天的一个单位的奶酪放置到第i天的花费：
    //第j天买来奶酪的花费(cost[j])，加上存储i-j天的花费(S*(i-j))
    ans+=Min*need[i];//累加每天的最小花费
  }
  cout<<ans;
  return 0;
}

到目前为止，我们就已经可以A掉本题了。但是 O(n^2) 的时间复杂度有点大，能不能再优化？

答案是肯定的。

O(n) 贪心优化算法

优化思路

贪心方法依然不变，现考虑对于第 i 天最优的 j 与第 i+1 天最优的 j 是否有什么关系。

不难发现，对于任意的 j（1\le j\le i，此处不是 i+1），第 j 天存储一个单位的奶酪到第 i+1 天比存储到第 i 天的花费都正好多了 S，这意味着，在不考虑 j=i+1 的情况下，第 i 天最优的 j 也是对于第 i+1 天最优的 j。

所以，我们只需要拿第 i 天最优的 j 与 j=i+1 的情况做对比即可。

优化代码实现

具体实现的方法见代码（改动地方有详细注释）：

#include <bits/stdc++.h>
using namespace std;
int need[10001],cost[10001];
int n,S;
inline int read()                        //以字符串形式读入数字可提速
{
  int x=0;
  char c=getchar();
  for(; c<'0'  || c>'9';  c=getchar());
  for(; c<='9' && c>='0'; c=getchar())
    x=(x<<3)+(x<<1)+c-'0';               //位运算优化即x*8+x*2=x*10
  return x;
}
int main()
{
  n=read(),S=read();
  for(int i=1; i<=n; i++)
    cost[i]=read(),need[i]=read();
  int Min=INT_MAX-S;//此处减去S是为了防止爆精度
  long long sum=0;
  for(int i=1; i<=n; i++)
  {
    Min=min(Min+S,cost[i]);
    //前一天最优的j在当天的花费：Min+S
    //当天花费：cost[i]
    sum+=Min*need[i];
  }
  cout<<sum;
  return 0;
}

Tips:

注意，答案可能超过 32 位长整型。

所以别忘了开 long long。