张三的酸奶厂：C++用贪心算法解POJ2393_Yogurt factory问题

POJ2393 Yogurt factory

题目链接：
POJ2393 Yogurt factory

简单理解一下题目：
张三开了一家酸奶场，在接下来N周里每周要给客户提供一定数量的酸奶，每周可以生产无限量的酸奶，就是可以选择一次生产完也可以分期生产，然后每周生产的成本不一样，而且提前生产的酸奶可以拿去储存，储存单价是固定的，我们需要给张三提供一个方案使得在满足酸奶供应的情况下，成本最小。

简单分析：
这题是个典型的贪心算法题，我们从第一周开始生产酸奶，后面每一周采用循环，找出最省钱的方案，比如第二周单位酸奶成本是100，但是第一周是90，而储存的成本是5，那么90+5＜100，所以应该选择第一周就把第二周的量生产了，然后储存起来，等到第二周再拿给客户。每一周的酸奶都只能在前面的周或者当前周生产，每个周都要考虑前面所有的周，比较一下哪个周的成本+储存单价*储存周数是最小的，就在成本最小的那一个周进行酸奶的生产。

AC代码：

#include<iostream>

using namespace std;

const int MAX_N = 100000;

int N, S;
long long Sum_price = 0;


struct node {
	int week, price, sum;
}Yogurt[MAX_N];

void solve()
{
	Sum_price += Yogurt[0].price * Yogurt[0].sum;
	for (int i = 1; i < N; i++)
	{
		int p = Yogurt[i].price;
		for (int j = 0; j < i; j++)
		{
			if ((Yogurt[j].price + S * (i - j)) < Yogurt[i].price)
			{
				p = Yogurt[j].price + S * (i - j);
			}
		}
		Sum_price += Yogurt[i].sum * p;
	}
}

int main()
{
	cin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		cin >> Yogurt[i].price >> Yogurt[i].sum;
	}
	solve();
	cout << Sum_price << endl;
	return 0;
}

/*
4 5
88 200
89 400
97 300
91 500
*/

做题心得：
这个题比较简单，一遍过了，已经好久没有一次过了，找回一点点信心也是好的哈哈哈哈哈哈哈哈哈哈哈