放牧代码和思想
专注自然语言处理、机器学习算法

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版)》练习题答案

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机