0w1

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