提出 #75559242

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n = sz(s);
        vector<int>a(n+1);
        vector<int>p(n+5);
        vector<int>dp(n+1);
        int sum = 0;
        for(int i = 1; i<=n; i++){
            a[i] = s[i-1] - '0';
            sum += a[i];
        }
        for(int i = 1; i<=n; i++){
            p[i] = p[i-1] + a[i];
        }
        auto cost = [&](int l, int r) -> int {
            if(a[l] == 9)return (int)1e9;
            if(l == r)return a[l];
            return a[l] + 1 + 9 * (r-l) + 1 - (p[r] - p[l]);
        };
        for(int i = 1; i<=n; i++){
            dp[i] = cost(0,i);
            for(int j = 0; j<i; j++){
                dp[i] = min(dp[i],dp[j] + cost(j+1,i));
            }
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果