记录编号	597228	评测结果	AAAAAAAAAA
题目名称	二分的代价	最终得分	100
用户昵称	HXF	是否通过	通过
代码语言	C++	运行时间	1.485 s
提交时间	2024-11-25 19:02:24	内存使用	48.70 MiB

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

template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=1e5+5,L=20,T=9*L+5;
char a[N];
int dp[N][T],last[N][10];

int main()
{
	freopen("changgao_cost.in","r",stdin);freopen("changgao_cost.out","w",stdout);
		scanf("%s",a+1);
		int n=strlen(a+1);
		rep(i,1,n)a[i]-='0';
		rep(i,1,n)
		{
			rep(j,1,9)last[i][j]=last[i-1][j];
			last[i][a[i]]=i;
		}
		rep(c,0,T-1)dp[n+1][c]=n;
		per(i,n,1)
		{
			rep(c,0,a[i]-1)dp[i][c]=i-1;
			int c=a[i];
			for(;dp[i][c-1]<n;++c)
			{
				int ans=i-1;
				per(j,min(c,9),1)
				{
					int i1=last[dp[i][c-j]+1][j];
					if(i1>=i)chmax(ans,dp[i1+1][c-j]);
				}
				dp[i][c]=ans;
			}
			if(i==1)printf("%d\n",c-1);
			for(;c<T;++c)dp[i][c]=n;
		}
}