第一篇 2021-10-26[USACO05MAR]Yogurt factory 机器工厂 - 洛谷https://www.luogu.com.cn/problem/P1376
目录
题目描述
小 T 开办了一家机器工厂，在?N个星期内，原材料成本和劳动力价格不断起伏，第?i?周生产一台机器需要花费?Ci??元。若没把机器卖出去，每保养一台机器，每周需要花费?S?元，这个费用不会发生变化。
机器工厂接到订单，在第?ii?周需要交付Yi??台机器给委托人，第?i?周刚生产的机器，或者之前的存货，都可以进行交付。
请你计算出这?n?周时间内完成订单的最小代价。
输入格式
第一行输入两个整数?N?和?S，接下来?NN?行每行两个数Ci??和 Yi?。
输出格式
输出一个整数，表示最少的代价。
注意范围：1<=n<=10000,1<=Ci<=5000,1<=S<=100,0<=Yi<=10000.
思路
贪心算法，找到每周的最小花费。f[i]为第i周花费最小的交互方法，用第i-1周加上保养的花费和第i周生产的花费求最小的f[i]=min(f[i-1]+s,c[i])。
结果定义long long，防止超过int的范围。
（贪心：不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。）
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//定义long long，防止爆int
ll n,s;
ll c[10010],y[10010];//存储费用和交互数量
ll f[10010];
ll sum=0;
int main(){
scanf("%lld%lld",&n,&s);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&c[i],&y[i]);
}
for(int i=1;i<=n;i++){
if(i==1){
f[i]=c[i];
}
else{
f[i]=min(c[i],f[i-1]+s);
}
sum=sum+f[i]*y[i];
}
printf("%lld",sum);
}