CFR 792 C. Divide by Three ( DP )
題意:
給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 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; }