[貪心策略]USACO Mar05 yogfac 奶酪工廠 解題報告

      USACO Mar05 yogfac 奶酪工廠 解題報告
 【問題描述】

奶牛們開辦了一個奶酪工廠來生產世界著名的約克奶酪。在接下來的 N (1<=N<=10000) 星期中，由於牛奶和勞動力的價格變化，奶酪的成本也在變化。因此奶酪工廠在第 i 個星期要花 C_i (1<=C_i<=5000) 分來生產一個單位的奶酪。 由於採用了最先進的技術，約克奶酪工廠在一個星期內可以生產任意多的奶酪。

約克奶酪工廠擁有一個無限大的倉庫， 每個星期生產的多餘的奶酪都會放在這裏。而且每個星期存放一個單位的奶酪要花費 S (1<=S<=100) 分，不過幸運的是由於採用了最先進的技術，奶酪在倉庫裏不會壞 ^_^

工廠最近收到了客戶 N 個星期的訂單，第 i 個星期要向客戶提供 Y_i (0<=Y_i<=10000) 個單位的奶酪。當然這些奶酪可以在第 i 個星期時生產，也可以從倉庫中拿取。

採用怎麼樣的生產策略纔會使約克工廠的花費最小呢？你能幫幫它們嗎？

【輸入格式】

* 第 1 行兩個整數： N 和 S

* 接下來的 N 行中，第 i 行的兩個數表示： C_i 和 Y_i

【輸出格式】

* 輸出僅一行，工廠生產的最小花費

【輸入輸出樣例】

factory.in

4 5

88 200

89 400

97 300

91 500

factory.out

126900

【輸入輸出樣例說明】

最佳生產方案如下：第一個星期生產 200 個單位的奶酪全部送給客戶，第二個星期生產 700 個單位的奶酪， 400 個送給客戶，另外 300 個放在倉庫。第三個星期把倉庫中的 300 個奶酪賣給客戶，第四個星期生產 500 個單位的奶酪賣給客戶。

【分析】

貪心策略，要算出某個星期最小的花費，只需要枚舉 從第一個星期 到 這個星期的生產+儲存的最小值，然後輸出總的花費即可。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int S;
long long Tot=0;

class Factory
{
public:
    long long Cost;
    long long Need;
}Fac[10002];

void init()
{
    cin>>N>>S;
    for (int i=1;i<=N;i++)
        cin>>Fac[i].Cost>>Fac[i].Need;
    return;
}

void work()
{
    for (int i=1;i<=N;i++)
    {
        long long tmp=Fac[i].Cost*Fac[i].Need;
        for (int j=1;j<=i-1;j++)
        {
            if(tmp> ( Fac[j].Cost * Fac[i].Need +(i-j)*S*Fac[i].Need) )
                tmp=Fac[j].Cost * Fac[i].Need +(i-j)*S*Fac[i].Need;
        }
        Tot+=tmp;
    }
    cout<<Tot<<endl;
}

int main()
{
    freopen("factory.in","r",stdin);
    freopen("factory.out","w",stdout);
    init();
    work();
    return 0;
}