CFR 264 C. Choosing Balls ( DP )

Problem - C - Codeforces

題意：
有 N 個球排一排，用價值 V[ i ] 和顏色 C[ i ] 描述。接著 Q 筆詢問，給你 A, B，要求一個序列的最大歡樂值。序列必須是升序的下標，歡樂值得計算方法為：若序列中某個下標 i 不為序列最小值，且前面一個下標 i - 1 的顏色 C[ i - 1 ] 和 C[ i ] 相同，那麼該元素的貢獻為 V[ i ] * B ; 否則該元素的貢獻為 V[ i ] * A。

資料規模：
The first line contains two integers n and q (1 ≤ n ≤ 1e5; 1 ≤ q ≤ 500). The second line contains n integers: v1, v2, ..., vn (|vi| ≤ 1e5). The third line contains n integers: c1, c2, ..., cn (1 ≤ ci ≤ n).
The following q lines contain the values of the constants a and b for queries. The i-th of these lines contains two integers ai and bi (|ai|, |bi| ≤ 1e5).
TL: 5000 ms
ML: 256 MB

解法：
考慮直接 O( N ) 解決一個詢問。顯然狀態可以描述為：
dp[ i ]：當前，以顏色 i 結尾的狀態下，最大可能貢獻總和
而需要的轉移是前一次的 dp[ i ] ，以及非 i 的 dp 值中最大的。
所以，只要維護最大的兩個 dp 值對應的顏色，就能達到常數時間更新。

時間 / 空間複雜度：
O( Q * N ) / O( N )

注意：
一定要保證最大兩個 dp 值對應的顏色不同，詳見第 37 行第一式。

int N, Q;
vi V;
vi C;

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

void solve(){
  for( int kase = 0; kase < Q; ++kase ){
    int A, B; cin >> A >> B;
    vl dp( N + 1, - ( 1LL << 60 ) );
    dp[ 0 ] = 0;
    int max1_col = 0, max2_col = -1;
    for( int i = 0; i < N; ++i ){
      if( dp[ C[ i ] ] == - ( 1LL << 60 ) ){
        dp[ C[ i ] ] = 1LL * B * V[ i ];
      } else{
        upmax( dp[ C[ i ] ], dp[ C[ i ] ] + 1LL * A * V[ i ] );
      }
      assert( max1_col != max2_col );
      if( max1_col != C[ i ] ){
        upmax( dp[ C[ i ] ], dp[ max1_col ] + 1LL * B * V[ i ] );
      } else if( max2_col != -1 ){
        upmax( dp[ C[ i ] ], dp[ max2_col ] + 1LL * B * V[ i ] );
      }
      if( dp[ max1_col ] < dp[ C[ i ] ] ){
        max2_col = max1_col;
        max1_col = C[ i ];
      } else if( max1_col != C[ i ] and ( max2_col == -1 or dp[ max2_col ] < dp[ C[ i ] ] ) ){
        max2_col = C[ i ];
      }
    }
    cout << *max_element( dp.begin(), dp.end() ) << endl;
  }
}