POJ 2393 Yogurt factory 题解 《挑战程序设计竞赛》

POJ - 2393

题目很简单，有一些需要注意的地方。

刚开始没有定义成long long的变量导致WA。

O(n²)的复杂度导致TLE。

学习@Lorazepam ，用了动态规划。

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long ll;
int n;
int s;
ll c[10005];
ll y[10005];

void solve() {
    ll res = 0;
    
    for (int i = 1; i < n; i++) {
        c[i] = min(c[i], c[i - 1] + s);  //每一周只需要和上周比较的原因是上周和上上周也比较过了。
    } 
    for (int i = 0; i < n; i++) {
        res += c[i] * y[i];
    }

    printf("%lld
", res);
}

int main() {
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c[i], &y[i]);
    }
    solve();
    return 0;
}