题目链接:http://acm.uestc.edu.cn/problem.php?pid=1307
windy数
Time Limit: 1000 ms Memory Limit: 65536 kB Solved: 104 Tried: 720
Submit
Status
Best Solution
Back
Description
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道,在A和B之间,包括A和B,总共有多少个windy数?
Input
包含两个整数,A B。
满足 1 <= A <= B <= 2000000000 。
Output
包含一个整数:闭区间[A,B]上windy数的个数。
Sample Input
1 10
Sample Output
9
Source
Windy
简单的数位DP,要求相邻的两个数之差大于等于2.
/*
* UESTC 1307
* windy数:不含前导0,相邻两个数字之差至少为2的正整数
* 求[A,B]之间的windy数,1<=A<=B<=2000000000
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[15][10];//dp[i][j]表示长度为i,最高位为j的windy数的个数
void init()
{
memset(dp,0,sizeof(dp));
for(int i=0;i<10;i++)
dp[1][i]=1;
for(int i=2;i<=10;i++)
for(int j=0;j<10;j++)
{
for(int k=0;k<=j-2;k++)
dp[i][j]+=dp[i-1][k];
for(int k=j+2;k<10;k++)
dp[i][j]+=dp[i-1][k];
}
}
int bit[20];
int calc(int n)
{
if(n==0)return 0;
int len=0;
while(n)
{
bit[++len]=n%10;
n/=10;
}
bit[len+1]=-10;
int ans=0;
bool flag=true;
for(int i=1;i<len;i++)//先把长度小于len的计入
for(int j=1;j<=9;j++)
ans+=dp[i][j];
for(int j=1;j<bit[len];j++)//最高位
ans+=dp[len][j];
for(int i=len-1;i>=1;i--)
{
for(int j=0;j<bit[i];j++)
if(abs(bit[i+1]-j)>=2)
ans+=dp[i][j];
if(abs(bit[i+1]-bit[i])<2)
{
flag=false;
break;
}
}
if(flag)ans++;
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int a,b;
init();
while(scanf("%d%d",&a,&b)==2)
{
printf("%d\n",calc(b)-calc(a-1));
}
return 0;
}