学步园

记忆化搜索的数位DP；

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

struct Calc{
	int dp[11];
	int digit[11];
	int sum[11];
	Calc(){memset(dp,-1,sizeof(dp));};

	__int64 dfs(int pos, int pre, int have, int doing)
	{
		if(pos==-1) return have;
		if(!doing && dp[pos]!=-1){ 
			if(pre==1) return pow(10,(double)pos+1)+dp[pos];
			else return dp[pos];
		}
		int end = doing?digit[pos]:9;
		__int64 ans = 0;
		if(pre == 1 && doing ) {ans+=sum[pos]+1;have=0;}
		
		for(int i=0; i<=end; i++)
		{
			int nhave = have;
			if(i == 1) nhave++;
			ans+=dfs(pos-1,i,nhave,doing&&(i==end));
		}
		if(!doing) dp[pos]=ans;
		return ans;
	}
	__int64 calc(int x){
		
		int i=0;
		int k=1;
		while(x)
		{
			digit[i] = x%10;
			sum[i] = digit[i]*k;
			if(i>0) sum[i] += sum[i-1];
			i++;
			k*=10;
			x/=10;
		}
		return dfs(i-1,0,0,1);
	}
}F;
int main()
{
	int n;while(~scanf("%d",&n)){
	
		printf("%I64d\n",F.calc(n));
	}
	return 0;
}