一本通1587【例 3】Windy 数
标签：show 答案 lap center row 输入 its alt sha
1587： 【例 3】Windy 数
时间限制: 1000 ms 内存限制: 524288 KB
题目描述
原题来自：SCOI 2009
Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。
Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？
样例
样例输入 1
样例输出 1
样例输入 2
样例输出 2
数据范围与提示
20% 的数据，满足 1≤A≤B≤10^6；
100% 的数据，满足 1≤A≤B≤2×10^9。
sol：windy数，也是很友好的数位dp，也像数字游戏一样搞一搞，dp[i][j][Bo1][Bo2]第i位，填的数字为j，是否是上界，是否是前导0就over了
#include using namespace std;
int Num[20],dp[20][10][2][2];
inline int dfs(int Weiz,int Shuz,bool Shangj,bool Qiand0)
{
if(dp[Weiz][Shuz][Shangj][Qiand0]) return dp[Weiz][Shuz][Shangj][Qiand0];
if(Weiz==1) return (dp[Weiz][Shuz][Shangj][Qiand0]=1);
int i,Up=(Shangj)?(Num[Weiz-1]):(9);
// printf("Up=%d\n",Up);
for(i=0;iif((Qiand0)||(abs(Shuz-i)>1))
{
bool Bo1=(Shangj&&i==Up),Bo2=(Qiand0&&i==0);
dp[Weiz][Shuz][Shangj][Qiand0]+=dfs(Weiz-1,i,Bo1,Bo2);
}
return dp[Weiz][Shuz][Shangj][Qiand0];
}
inline int Solve(int n)
{
if(n==0) return 1;
memset(dp,0,sizeof dp);
*Num=0;
while(n)
{
Num[++*Num]=n%10;
n/=10;
}
int i,ans=0;
ans+=dfs(*Num,0,0,1);
// printf("Beg ans=%d\n",ans);
for(i=1;i)
{
ans+=dfs(*Num,i,0,0);
}
ans+=dfs(*Num,Num[*Num],1,0);
return ans;
}
int main()
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",Solve(r)-Solve(l-1));
return 0;
}
/*
input
1 10
output
9
input
25 50
output
20
*/
View Code
一本通1587【例 3】Windy 数
标签：show 答案 lap center row 输入 its alt sha
原文地址：https://www.cnblogs.com/gaojunonly1/p/10360015.html
评论