POJ 2393 Yogurt factory 《挑战程序设计竞赛(第2版)》练习题答案

2.2 一往直前！贪心法 其他

POJ 2393 Yogurt factory

奶牛们建了一家酸奶厂，在N周内每周需要出货Y_i单位酸奶，第i周成本为C_i，储存费为每周Y。求总体最低成本。

贪心策略是维持每周的最低单位成本，每周可能用上周剩下的，也可能生产新的。于是该周单位成本可能为上一周的单位成本加上储存费，也可能为该周的单位成本。

#include <iostream>
using namespace std;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N, S;
	cin >> N >> S;
	int P = 5000;
	long long costs = 0;
	for (int i = 0; i < N; ++i)
	{
		int C, Y;
		cin >> C >> Y;
		P = min(P + S, C);
		costs += P * Y;
	}
	cout << costs << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2393 Yogurt factory 《挑战程序设计竞赛(第2版)》练习题答案