D. Polycarp and Div 3

题目链接

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

题解

中档题。题意大概是将给定的数字序列分成若干个区间,使得能被3整除的区间数最大。
动态规划(大概)。判断从头到当前位置的能被3整除的最大区间数为max(上一个位置的值,从当前位置往前得到第一个能被3整除的区间的位置的值+1)。如果括号中后一个值为判断整个序列的话会超时,这样是一个正确高效的优化方法。

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int a[200005],num;
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        num = 0;
        a[i + 1] = a[i];
        for (int j = i; j >= 0; j--) {
            num += s[j] - '0';
            if (num % 3 == 0) { 
                a[i + 1] = max(a[j] + 1, a[i + 1]);
                break;
            }
        }
    }
    cout << a[s.size()];
}

标签: dp, number theory

添加新评论