数位dp

区间数位和最大值

若当前要求[l,r]的数位和，等价于求对于最后一个数位b，求b+FUNC[ceil((l-b)/10,floor((r-b)/10)]。

注意l>r时不合法，应该返回-inf。

vector<int> ksm10{1};

int max0(int x,int lim) {
    int ret = x;
    for (int i = 1; i <= 18; ++i) {
        if ((ret + ksm10[i] - 1) / ksm10[i] * ksm10[i] <= lim) {
            ret = (ret + ksm10[i] - 1) / ksm10[i] * ksm10[i];
        } else {
            return ret;
        }
    }
    return ret;
}

map<pair<int,int>,int> memo;

int dfs(int l,int r) {
    if (l > r) {
        return -999;
    }
    if (r == 0) {
        return 0;
    }
    if (memo.contains({l, r}))return memo[{l, r}];
    int ret = 0;
    for (int b = 0; b <= min<int>(9, r); ++b) {
        ret = max(ret, b + dfs((l - b + 9) / 10, (r - b) / 10));
    }
    // de(l, r, ret);
    return memo[{l, r}] = ret;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    for (int i = 0; i < 18; ++i) {
        ksm10.push_back(ksm10.back() * 10);
    }
    cin >> n;
    while (n--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int l = l1 + l2, r = r1 + r2;
        int mid = max0(l, r);
        int m1 = dfs(l, mid - 1), m2 = dfs(mid, r);
        cout << max(m1, m2) << endl;
        memo.clear();
    }
    return 0;
}