- 科技
- Windy数（数位dp）
思路：dp[i]表示从0——i满足条件的所有数的数量，那么求dp[r]-dp[l-1]，我们按每一位去考虑首先我们要算出每一位的满足条件的数量f[i][j]表示共有i位且最高位为j满足条件的数的个数我们枚举0-9每一位满足条件的情况每一位都是由前一位累加得的。f[i][j]+=f[i-1][j],dp时我们根据前一位看当前位加上windy数，如果不满足windy数直接退出，最后再加上1-N-1位的每种以0结尾的windy数的个数
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e9+7;
const int N
=2e6+10;
const int M
=1e3+10;
const int inf
=0x3f3f3f3f;
const int maxx
=2e5+7;
const double eps
=1e-6;
int gcd(int a
,int b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll
qsm(int a
,int b
,int p
)
{
ll res
=1%p
;
while(b
)
{
if(b
&1)
res
=res
*a
%p
;
a
=1ll*a
*a
%p
;
b
>>=1;
}
return res
;
}
int f
[100][100];
void init()
{
for(int i
=0;i
<=9;i
++) f
[1][i
]=1;
for(int i
=2;i
<=15;i
++)
{
for(int j
=0;j
<=9;j
++)
{
for(int k
=0;k
<=9;k
++)
{
if(abs(j
-k
)>=2)
f
[i
][j
]+=f
[i
-1][k
];
}
}
}
}
int dp(int n
)
{
if(!n
)return 0;
vector
<int> num
;
while(n
) num
.push_back(n
%10),n
/=10;
int res
=0;
int last
=-2;
for(int i
=num
.size()-1;i
>=0;i
--)
{
int x
=num
[i
];
for(int j
=i
==num
.size()-1;j
<x
;j
++){
if(abs(j
-last
)>=2) res
+=f
[i
+1][j
];
}
if(abs(x
-last
)>=2) last
=x
;
else break;
if(!i
) res
++;
}
for(int i
=1;i
<num
.size();i
++){
for(int j
=1;j
<=9;j
++){
res
+=f
[i
][j
];
}
}
return res
;
}
int main()
{
init();
int l
,r
;
cin
>>l
>>r
;
cout
<<dp(r
)-dp(l
-1)<<endl
;
return 0;
}
Processed:
0.024, SQL:
9
