# CFR 792 C. Divide by Three ( DP )

dp[ i ][ j ] : 已考慮前 i 個數字，現在除以 3 餘 j，此時最大保留數。

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