题目
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
题解
数位dp水题，getans(n)搜索0-n之间的答案，则对于区间[l,r]最后答案为getans(r)-getans(l-1)
getans里用dfs对n的每一位进行枚举
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
const int maxn=1000010;
using namespace std;
typedef long long LL;
const int MOD=(int)(1e9+7);
int bit[20],dp[20][10];
int (int n);
int dfs(int pos,int st,int limit,int maxbit);
int main(){
int l,r;
while(cin>>l>>r){
cout<<getans(r)-getans(l-1)<<endl;
}
return 0;
}
int (int n){
int p=0,ans=0;
while(n){
bit[++p]=n%10;
n/=10;
}
return dfs(p,0,1,1);
}
int dfs(int pos,int st,int limit,int maxbit){
if(pos==0)
return 1;
if(!limit&&!maxbit&&dp[pos][st])
return dp[pos][st];
int mx=limit?bit[pos]:9;
int ans=0;
for(int i=0;i<=mx;i++){
if(abs(i-st)<2&&!(maxbit))continue;
ans+=dfs(pos-1,i,limit&&i==mx,maxbit&&i==0);
}
if(!limit&&!maxbit)dp[pos][st]=ans;
return ans;
}
|
近期评论