CFR 67 A. Partial Teacher ( DP, Greedy )
Problem - A - Codeforces
WA 好多次...
題意:
有 N 個數字,給你兩兩之間的大小關係,左大,左小,或相等。求總和最小的合法數列長相。
資料規模:
The first line of input contains the number of students n (2 ≤ n ≤ 1000). The second line gives (n - 1) characters consisting of "L", "R" and "=". For each pair of adjacent students "L" means that the left student has higher marks, "R" means that the right student has higher marks and "=" means that both have equal marks.
TL: 1000 ms
ML: 256 MB
解法:
如果前一個比較是 <,那麼當前的數字為前面的 +1 ; 如果前一個比較是 =,那麼當前的數字等於前面的 ; 如果前一個比較是 >,那麼當前的數字為 1,如果產生矛盾,則需要的數字都 +1。
時間 / 空間複雜度:
O( N^2 )
注意:
給兩個可能有用的 case 測測看:
9 RRRRRRLL : 1 2 3 4 5 6 7 2 1
5 LLLL : 5 4 3 2 1
int N; string cmp; void init(){ cin >> N; cin >> cmp; } vi ans; void preprocess(){ ans = vi( N ); ans[ 0 ] = 1; for( int i = 0; i < N - 1; ++i ){ if( cmp[ i ] == '=' ){ ans[ i + 1 ] = ans[ i ]; } else if( cmp[ i ] == 'L' ){ ans[ i + 1 ] = 1; if( ans[ i ] == 1 ){ for( int j = i; j >= 0; --j ){ ++ans[ j ]; if( j - 1 < 0 or cmp[ j - 1 ] == 'R' ){ break; } if( cmp[ j - 1 ] == 'L' and ans[ j - 1 ] > ans[ j ] ){ break; } } } } else{ ans[ i + 1 ] = ans[ i ] + 1; } } } void solve(){ for( int i = 0; i < N; ++i ){ cout << ans[ i ] << " \n"[ i + 1 == N ]; } }