AOJ 2431 House Moving ( DP + Segment Tree )

House Moving | Aizu Online Judge
JOI 11 Day4 Bookshelf ( DP + Segment Tree ) - 0w1
とほぼ同じ。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
#define int long long

struct itvt{
    int maxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = 0, int _r = 0): maxv(0), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        maxv = max( lc->maxv, rc->maxv );
    }
    void update(int k, int v){
        if( lb == rb ){
            maxv = v;
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->update( k, v );
        else rc->update( k, v );
        pull();
    }
    int qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return 0;
        if( ql <= lb && rb <= qr ) return maxv;
        int res = 0;
        res = max( res, lc->qmax( ql, qr ) );
        res = max( res, rc->qmax( ql, qr ) );
        return res;
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    return t;
}

int n;
int x[ MAXN ];

void solve(){
    itvt *root = buildItvt( 1, n );
    int sum = 0, maxnmv = 0;
    for(int i = 1; i <= n; ++i){
        sum += x[ i ];
        int nmv = root->qmax( 1, x[ i ] - 1 ) + x[ i ];
        maxnmv = max( maxnmv, nmv );
        root->update( x[ i ], nmv );
    }
    cout << sum - maxnmv << endl;
}

signed main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> x[ i ];
    solve();
    return 0;
}