记录编号	600926	评测结果	AAAAAAAAAA
题目名称	4074.二分的代价	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	4.082 s
提交时间	2025-05-21 17:28:55	内存使用	39.03 MiB

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll N=1e5+5,K=140,U=141;

char s[N];
int a[N];
int n;
int f[N][U];
int las[N][10];

int main()
{
	freopen("changgao_cost.in","r",stdin);
	freopen("changgao_cost.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i){
        for(int l=1;l<=9;++l) las[i][l]=las[i-1][l];
        a[i]=s[i]^48;
        las[i][a[i]]=i;
    }
    for(int l=1;l<=9;++l) las[n+1][l]=las[n+2][l]=las[n][l];
    for(int i=0;i<=K;++i) f[n+1][i]=f[n+2][i]=n;
    for(int i=1;i<=K;++i)
        for(int l=1;l<=n;++l)
            if(a[l]>i) f[l][i]=l-1;
            else {
                f[l][i]=max(f[l][i-1],l);
                if(f[l][i]==n) continue;
                int sj=min(9,i);
                for(int j=1;j<=sj;++j)
                    f[l][i]=max(f[l][i],f[las[f[l][i-j]+1][j]+1][i-j]);
            }
    int ans=0;
    for(int i=0;i<=K;++i)
        if(f[1][i]>=n){
            ans=i;
            break;
        }
    printf("%d",ans);
    return 0;
}