0w1

CFR 234 C. Weather ( DP )

Problem - 234C - Codeforces
題意:
給一個序列,改變最少的數字使得存在一個邊界使得左邊都是負數,右邊都是正數。
解法:
預處理正、負數數量的前綴和,接著枚舉邊界更新答案 。

int N;
vi T;

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

vi pp;
vi pn;

void preprocess(){
    pp = pn = vi( N + 1 );
    for( int i = 0; i < N; ++i )
        pp[ i + 1 ] = pp[ i ] + ( 0 < T[ i ] ),
        pn[ i + 1 ] = pn[ i ] + ( T[ i ] < 0 );
}

void solve(){
    int ans = INF;
    for( int i = 1; i < N; ++i )
        upmin( ans, pp[ i ] + pn[ N ] - pn[ i ] );
    cout << ans + N - ( pp[ N ] + pn[ N ] ) << endl;
}