蒟蒻求助!10分
查看原帖
蒟蒻求助!10分
163714
Wanna_Accepted楼主2021/1/28 15:40
#include<bits/stdc++.h>
using namespace std;
const int N=15;
#define ll long long
ll dp[N][N];
void init()
{
	for(int i=0;i<=9;i++)dp[1][i]=1;
	for(int i=2;i<=N-2;i++)
	{
		for(int j=0;j<=9;j++)
		{
		   for(int k=0;k<=j-2;k++)
		   dp[i][j]+=dp[i-1][k];
		   for(int k=j+2;k<=9;k++)
	       dp[i][j]+=dp[i-1][k];
		}
	}
}
ll DP(ll n)
{
	if(n==0)return 0;
	int last=-2;
	int ret=0;
	bool flag=0;
	vector<int> q;
	while(n)
	{  
		q.push_back(n%10);
		n/=10;
	}
	int len=q.size()-1;
	for(int i=len;i>=0;i--)
	{
		int x=q[i];
		if(i==len)ret+=dp[i][1];
		for(int j=last+2;j<x;j++)
		ret+=dp[i+1][j];
		if(x>0)
		{
			int now;
		   if(last-2<x-1)now=last-2;
		   else now=x-1;
		   for(int j=now;j>=0;j--)
	        ret+=dp[i+1][j];
		}
		if(abs(x-last)<2)
		{
			return ret;
		}
		last=x;
	}
    if(len==0)ret--;
	ret++;
	//for(int i=0;i<=len;i++)ret-=dp[i+1][0];
	return ret;
}
int main()
{
	init();
//	for(int i=1;i<=N;i++)
//	{
//		for(int j=0;j<=9;j++)
//		{
//			printf("i:%d j:%d %d\n",i,j,dp[i][j]);
//		}
//	}
	ll l,r;
	scanf("%lld%lld",&l,&r);
	printf("%lld",DP(r)-DP(l-1));
	return 0;
}
2021/1/28 15:40
加载中...