D. Polycarp and Div 3 | Codeforces Round #496 (Div. 3)

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので

dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」

のようなDPを解く。

int dp[200005][3];

int main() {
    MEM(dp, -1);
    dp[0][0] = 0;

    string S;
    cin >> S;
    int N = sz(S);

    rep(i, N) {
        int a = S[i] - '0';
        rep(j, 3) if(dp[i][j]!=-1){
            smax(dp[i + 1][(j + a) % 3], dp[i][j] + ((j+a)%3==0));
            smax(dp[i + 1][a % 3], dp[i][j] + (a % 3 == 0));
        }
    }
    int re = -1;
    rep(j, 3)smax(re, dp[N][j]);
    cout << re << endl;
}