机器工厂

洛谷-P1376-机器工厂

实现

// O(n^2)
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 10010;
struct node {
    int c, y;
};
int n, s;
node a[N];

int main () {
    cin >> n >> s;
    for (int i = 1; i <= n; ++ i) cin >> a[i].c >> a[i].y;

    LL res = 0;
    for (int i = 1; i <= n; ++ i) {
        int val = a[i].c; // 最低的单位成本
        for (int j = 1; j <= i - 1; ++ j)
            val = min(val, a[j].c + (i - j) * s);
        res += val * a[i].y;
    }
    cout << res << endl;
    return 0;
}

// O(n)
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long LL;
const int N = 10010;
struct node {
    int c, y;
};
int n, s;
node a[N];

int main () {
    cin >> n >> s;
    for (int i = 1; i <= n; ++ i) cin >> a[i].c >> a[i].y;

    LL res = 0;
    int val = inf;
    for (int i = 1; i <= n; ++ i) {
        val = min(a[i].c, val + s); // 优化
        res += val * a[i].y;
    }
    cout << res << endl;
    return 0;
}