CFR 269 B. Greenhouse Effect ( LIS )

Problem - 269B - Codeforces
題意：
給一堆東西的編號和位置，保證輸入位置是由小到大，操作可以將任意一個東西移到任意一個地方，求最少操作數使編號隨位置非嚴格遞增。
解法：
就是 N - LIS。

int N, M;
vi S;
vd X;

void init(){
    cin >> N >> M;
    S = vi( N );
    X = vd( N );
    for( int i = 0; i < N; ++i )
        cin >> S[ i ] >> X[ i ];
}

vi dp;

void preprocess(){
    dp = vi( N, 1 );
    for( int i = 0; i < N; ++i )
        for( int j = i + 1; j < N; ++j )
            if( S[ i ] <= S[ j ] )
                upmax( dp[ j ], dp[ i ] + 1 );
}

void solve(){
    cout << N - *max_element( dp.begin(), dp.end() ) << endl;
}