题目链接

Yogurt factory POJ - 2393

思路

每周的单价增长率相同，因此当前周最优单价为min(之前最小单价+一周储存费，当前周单价)。

时间复杂度

$$ O(N) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    long long ans = 0;

    int n, k;
    scanf("%d%d", &n, &k);// don't forget &
    int mi = INF;
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);// don't forget &
        mi = min(mi + k, x);
        ans += 1LL * mi * y;
    }
    printf("%lld", ans);
    return 0;
}