Brief description:

略。）

Analysis:

const int N = int(5e4) + 9;

VII II, I; LL f[N]; int q[N], cz, op;
int n;

#define k I[i].fi
#define x(j) I[j+1].se
#define y(j) f[j]
#define eval(j) ((LL)k*x(j)+y(j))

LL det(LL x1, LL y1, LL x2, LL y2){
    return x1*y2 - x2*y1;
}

int dett(int p0, int p1, int p2){
    LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));
    return t < 0 ? -1 : t > 0;
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    II.resize(RD(n)); REP(i, n) RD(II[i].fi, II[i].se);

    SRT(II); II.PB(MP(INF, 0)); I.PB(MP(0, INF)); REP(i, n){
        while (I.back().se <= II[i].se) I.pop_back();
        I.PB(II[i]);
    }

    /*n = SZ(I)-1; REP_1(i, n){
        f[i] = INFF;
        REP(j, i) checkMin(f[i], (LL)I[i].fi*I[j+1].se + f[j]);
        cout << f[i] << endl;
    }*/

    n = SZ(I)-1; cz = 0, op = 0; REP_1(i, n){
        while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz; f[i] = eval(q[cz]);
        while (cz < op && dett(q[op-1], q[op], i) > 0) --op; q[++op] = i;
        //cout << f[i] << endl;
    }

    cout << f[n] << endl;
}

Posted by xiaodao
Category: 日常