洛谷 P1376 [USACO05MAR]Yogurt factory 机器工厂 题解

本蒟蒻第一篇题解

题目传送门
拿到题第一眼觉得是动归，想着想着就发现能用贪心做，就是把之前制造花费的成本和这周的比较，哪个好用那个就行了。

清明时节雨纷纷，不开longlong就断魂

详情看代码：

#include <iostream>
using namespace std;
int c[10005], y[10005]; //第i周生产的成本和每周的订单数
int main() {
	int n, s, b = 0;//有n周，每周保养一台机器要s元，b表示之前成本最低的一周（请不要想到别处）
	long long ans = 0;//答案，要开long long
	cin >> n >> s;
	c[0] = 1e4;//防止有第0周的情况
	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> y[i];
		ans += min(c[i] * y[i], (c[b] + s * (i - b)) * y[i]);//核心，将答案加上最优解
		if (c[i] < (c[b] + s * (i - b)))
			b = i;//如果当前成本比之前最优成本小，最优周更新为当前周
	}
	cout << ans;//输出答案
	return 0;//好习惯
}

最后奉劝大家一句：珍爱生命，远离抄袭。

希望这篇题解对你有帮助，谢谢！