RT
我的代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long 
using namespace std;
ll f[20][10][20][3]; 
ll l,r; 
int n,a[20],b[20]; 
ll dfs(int k,int x,int sum,int flag) //位数 当前数 0的数量 借位标记
{
	if(k==n) 
	{
	    if(flag==2) return 0;
	    return sum;
	}
	if(f[k][x][sum][flag]!=-1) return f[k][x][sum][flag]; 
	ll s=sum; 
	for(int i=0;i<=9;i++) 
	if(flag==0||flag==2) 
	s=s+dfs(k+1,i,sum+(i==0),flag);
	else 
	{
	    int Next;
		if(i<a[k+1]) Next=0;
		if(i==a[k+1]) Next=1;
		if(i>a[k+1]) Next=2;
		s=s+dfs(k+1,i,sum+(i==0),Next);
	}
	return f[k][x][sum][flag]=s; 
}
ll solve(ll x)
{
	if(x<=0) return x; 
	n=0;
	while(x>0) 
	{
	    n++;
		a[n]=x%10;
		x=x/10;
	}
	for(int i=1;i<=n;i++) b[n-i+1]=a[i];
	for(int i=1;i<=n;i++) a[i]=b[i];
	for(int i=1;i<=n;i++) 
	for(int j=0;j<=9;j++) 
	for(int k=0;k<=n;k++) 
	for(int t=0;t<=2;t++) f[i][j][k][t]=-1; 
	ll res=0; 
	int flag; 
	for(int i=1;i<=9;i++) 
	{
		if(i<a[1]) flag=0;
		if(i==a[1]) flag=1;
		if(i>a[1]) flag=2; 
	    res=res+dfs(1,i,0,flag);
	}
	return res; 
}
int main()
{
	while(1) 
	{ 
	    scanf("%lld%lld",&l,&r);
	    if(l<0||r<0) break; 
	    if(l>r) swap(l,r); 
		printf("%lld\n",solve(r)-solve(l-1));
	}
    return 0;
}

• 布吉岛，直接算是O(lg n)，都要94ms，估计数据组数比较多。另外这题用不着dp啊（附代妈） (979) KatrineYang 2016-07-15 09:03:28