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; }