POJ2393贪心

题意：奶牛们收购了一家世界著名的酸奶工厂Yucky Yogurt. 在接下来的 N (1 <= N <= 10,000) 周,牛奶和人工的价格每周会波动，以致于第i周需要花公司 C_i (1 <= C_i <= 5,000) 美分来生产一个单位的酸奶.
Yucky Yogurt 拥有一个仓库，可以以S (1 <= S <= 100)美分每单位每周的价格储存没用的酸奶。酸奶不会变质，而且仓库足够大。
Yucky Yogurt每周要交货 Y_i (0 <= Y_i <= 10,000) 单位的酸奶给它的客户。输出最少的费用。

题解：每次都取局部最优解，然后将所有的最小值相加，就是整体的最小值。

贪心思路：利用dp得到每周的最小值，dp[i]为第i周的最小值，因为最小值的来源是min(dp[i-1]+S,C[i])

为什么不可能是C[i-2]+2S:因为dp[i-1]<=C[i-2]+S,所以dp[i]<=dp[i-1]+S<=C[i-2]+2S，其余情况同理排除

#include<stdio.h>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long ll;

ll C[], Y[];

ll dp[];

int main(void)

{

    ios::sync_with_stdio(false);

    int N, S;

    cin >> N >> S;

    for (int i = ; i <= N; i++)

        cin >> C[i] >> Y[i];

    dp[] = C[];

    ll sum = dp[]*Y[];

    for (int i = ; i <= N; i++)

    {

        dp[i] = min(C[i], dp[i - ] + S);

        sum += dp[i] * Y[i];

    }

    cout << sum << endl;

    return ;

}

巴特西

POJ2393贪心

最新文章

热门文章