AcWing 1083. Windy数
原题链接
中等
作者:
wangyj
,
2021-01-21 09:20:59
,
所有人可见
,
阅读 400
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int f[11][10];
int DP(int n)
{
if(!n)return 0;
vector<int>num;
while(n)num.push_back(n%10),n/=10;
int ans=0,end=-2,i,j,x;
for(i=num.size()-1;i>=0;i--){
x=num[i];
for(j=i==num.size()-1;j<x;j++)if(abs(j-end)>=2)ans+=f[i+1][j];
if(abs(x-end)>=2)end=x;
else break;
if(!i)ans++;
}
for(i=1;i<num.size();i++)for(j=1;j<=9;j++)ans+=f[i][j];
return ans;
}
int main()
{
int i,j,k,l,r;
for(i=0;i<=9;i++)f[1][i]=1;
for(i=2;i<11;i++)for(j=0;j<=9;j++)for(k=0;k<=9;k++)if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
scanf("%d%d",&l,&r);
printf("%d\n",DP(r)-DP(l-1));
return 0;
}