记录编号	597318	评测结果	AAAAAAAAAA
题目名称	二分的代价	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	4.100 s
提交时间	2024-11-26 16:31:47	内存使用	105.74 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 1e5 + 5, M = 205;
char s[N];
int n, a[N];
int f[N][M];
int p[N][15];
signed main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i ++){
        a[i] = s[i] - '0';
        for(int j = 1; j <= 9; j ++){
            p[i][j] = p[i - 1][j];
        }
        p[i][a[i]] = i;
    }
    for(int j = 0; j < M; j ++){
        f[n + 1][j] = n;
    }
    for(int j = a[n]; j < M; j ++){
        f[n][j] = n;
    }
    for(int i = n - 1; i >= 1; i --){
        f[i][a[i]] = i;
        for(int j = a[i] + 1; j < M; j ++){
            f[i][j] = f[i][j - 1];
            for(int k = 1; k <= j && k <= 9; k ++){
                f[i][j] = max(f[i][j], f[p[f[i][j - k] + 1][k] + 1][j - k]);
            }
        }
    }
    for(int j = 0; j < M; j ++){
        if(f[1][j] >= n){
            printf("%lld", j);
            return 0;
        }
    }
    return 0;
}