贪心牛牛牛

poj 2393

鱼宝收购了一家酸奶厂。
在接下来的 N（1 <= N <= 10,000）周里，由于牛奶的价格和工人的工资每周都会有所波动，因此第 i 周生产 1 单位的酸奶将花费 C_i (1 <= C_i <= 5,000) 元。
鱼宝的酸奶厂很厉害，每周想生产多少酸奶就生产多少酸奶。

鱼宝还有一个可以存储暂未交付的酸奶的仓库。每周存放 1 单位酸奶的费用固定为 S (1 <= S <= 100) 元。
幸运的是，在仓库存储的酸奶不会变质，且仓库足够大，想存多少酸奶就存多少酸奶。

鱼宝每周都要向客户交付 Y_i (0 <= Y_i <= 10,000) 单位的酸奶（Y_i 表示第 i 周需要交付酸奶的量）但是鱼宝并不擅长计算题，因此想请你帮帮忙，帮助鱼宝找到一种方法，尽可能的降低 N 周内的生产成本，且要让第 i 周生产的酸奶和已经存储的酸奶可以满足这周的要求。

Input

* 第 1 行: 两个由空格隔开的整数: N 和 S

* 第 2 ~ N+1 行: 第 i+1 行包含两个由空格隔开的整数: C_i 和 Y_i.

Output

* 第 1 行: 第 1 行包含一个整数: 满足当周酸奶需求的最低总成本。 请注意，结果可能大于 32 位整型的范围。

Sample Input

4 5
88 200
89 400
97 300
91 500

Sample Output

126900

Hint

输出详解：
第一周，生产 200 单位的酸奶并全都交付；第二周，生产 700 单位的酸奶，交付 400 单位的酸奶，存储 300 单位的酸奶；第三周，把存储的 300 单位的酸奶交付出去；第四周，生产 500 单位的酸奶并交付出去。

题解：把仓库的费用也算进去！！！！！！

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1e4+1;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct node {
    ll c,y; 
}nodes[maxn];
int main() {
    ll n,s;
    cin>>n>>s;
    nodes[0].c=inf;
    for(int i=1;i<=n;i++) {
        scanf("%lld%lld",&nodes[i].c,&nodes[i].y);
    }
    ll ans=0;
    for(int i=1;i<=n;i++) {
        nodes[i].c=min(nodes[i].c,nodes[i-1].c+s);
        ans+=nodes[i].c*nodes[i].y;
    }
    cout<<ans<<endl;
    return 0;
}