P2602 [ZJOI2010] 数字计数

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
#define debug() cout<<"qwq"<<endl
#define int long long
using namespace std;

const int N=1500;
string a,b;
int ansa[N],ansb[N];
int pre_a[N],g[N][N];
int dp[N][N];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline void write(int x)
{
	if (!x)
	{
		putchar('0');
		return;
	}
	int len = 0, k1 = x, c[40];
	if (k1 < 0) k1 = -k1, putchar('-');
	while (k1) c[len ++ ] = k1 % 10 ^ 48, k1 /= 10;
	while (len -- ) putchar(c[len]);
}

void solve(string x,int *ans)
{
	memset(g,0,sizeof(g));
	memset(pre_a,0,sizeof(pre_a));
	memset(dp,0,sizeof(dp));
	memset(ans,0,sizeof(ans));
	int cnt=0;
	int yx[N];
	for(int i=0;i<x.length();i++)
	{
		int y=x[i];
		cnt++;
		pre_a[cnt]=pre_a[cnt-1]*10+y;
		yx[cnt]=y;
		//cout<<y<<endl;
		for(int i=0;i<=9;i++)
		{
			if(i==y) g[cnt][i]=g[cnt-1][i]+1;
			else g[cnt][i]=g[cnt-1][i];
		}
		x/=10;
		//cout<<x<<endl;
	}
	for(int i=1;i<=cnt;i--)
	{
	    for(int j=0;j<=9;j++)	
		{
			dp[i][j]=dp[i-1][j]*10 + (pre_a[i-1]-1) + (yx[i]*g[i-1][j]) + (yx[i]>0 ? 1:0) +(j!=0? 1:0); 
		}
	}
	for(int i=0;i<=9;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			ans[i]=max(ans[i],dp[j][i]);
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		ans[yx[i]]++;
	}
}

signed main()
{
	a=read();
	b=read();
	solve(a-1,ansa);
	solve(b,ansb);
	for(int i=0;i<=9;i++)
	{
		//cout<<ansb[i]<<" "<<ansa[i]<<endl;
		write(ansb[i]-ansa[i]);
		cout<<" ";
	}
	return 0;
}

rt