CFR 792 C. Divide by Three ( DP )

Problem - C - Codeforces

題意：
給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 3 的倍數。刪除後不得有前導 0。輸出方案。

資料規模：
長度 ≤ 1e5

解法：
刪除最少等價於保留最多。
dp[ i ][ j ] : 已考慮前 i 個數字，現在除以 3 餘 j，此時最大保留數。
注意遞推時的乘以 10 的時機，以及逆推答案時要除以 10。

時間 / 空間複雜度：
O( LEN )

#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
  if( x >= v ) return 0;
  x = v; return 1;
}

const int MAXN = ( int ) 1e5;

string seq;

int dp[ MAXN + 1 ][ 3 ];
int dc[ MAXN + 1 ][ 3 ];

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> seq;
  }
  {
    for( int i = 0; i <= seq.size(); ++i ){
      for( int j = 0; j < 3; ++j ){
        dp[ i ][ j ] = - ( int ) 1e8;
      }
    }
    for( int i = 0; i < seq.size(); ++i ){
      if( seq[ i ] != '0' and upmax( dp[ i + 1 ][ ( seq[ i ] - '0' ) % 3 ], 1 ) ){
        dc[ i + 1 ][ ( seq[ i ] - '0' ) % 3 ] = 1;
      }
      for( int j = 0; j < 3; ++j ){
        if( dp[ i ][ j ] == - ( int ) 1e8 ) continue;
        if( upmax( dp[ i + 1 ][ ( j * 10 + seq[ i ] - '0' ) % 3 ], dp[ i ][ j ] + 1 ) ){
          dc[ i + 1 ][ ( j * 10 + seq[ i ] - '0' ) % 3 ] = 1;
        }
        if( upmax( dp[ i + 1 ][ j ], dp[ i ][ j ] ) ){
          dc[ i + 1 ][ j ] = 0;
        }
      }
    }
  }
  {
    if( dp[ seq.size() ][ 0 ] <= 0 ){
      for( int i = 0; i < seq.size(); ++i ){
        if( seq[ i ] == '0' ){
          cout << "0\n";
          exit( 0 );
        }
      }
      cout << -1 << "\n";
      exit( 0 );
    }
    string ans;
    for( int i = seq.size(), j = 0; i; --i ){
      if( dc[ i ][ j ] ){
        ans += seq[ i - 1 ];
        j = ( j - seq[ i - 1 ] + '0' + 33 ) % 3;
        ( j *= 10 ) %= 3;
      }
    }
    reverse( ans.begin(), ans.end() );
    cout << ans << "\n";
  }
  return 0;
}