P2657 [SCOI2009]windy数

题解

数位DP板子题

f[ i ][ j ] 表示长度为 i 的数字，最高温填的数字是  j  的时候，windy数的个数

f[ i ][ j ] = Σ f[ i ][ k ] ( abs(k-j)>=2 )

 

代码

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int aa,bb;
int f[11][10];
//f[i][j] 从后往前数第i位填了数字j的windy数个数
//或者可以理解为长度为i的数字，最高位填了数字j的windy数个数 

void pre()   //预处理 
{
    for(int i=0;i<=9;i++) f[1][i]=1;
    //单数位的数字也是windy数 
    
    for(int i=2;i<=10;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 work(int x)  //1~x-1中有多少个windy数 
{
    int ans=0;
    int a[11],len=0;
    while(x)  //存下x的各位数字 
    {
        a[++len]=x%10;
        x/=10;
    }
    
    for(int i=1;i<len;i++)
      for(int j=1;j<=9;j++)
        ans+=f[i][j];
    //长度比x小的数字一定是合法的 
    
    for(int i=1;i<=a[len]-1;i++)
        ans+=f[len][i];  
    //最高位数字比x最高位小的也一定合法 
    
    for(int i=len-1;i>=1;i--)  //从高位向低位枚举 
    {
        for(int j=0;j<=a[i]-1;j++) //x是上界，不可以超过x ，j是第i位上的数字 
           if(abs(j-a[i+1])>=2) ans+=f[i][j]; //和上一位比较，合法 
        if(abs(a[i+1]-a[i])<2) break; //上一位和自己比较，不合法，直接退出for循环 
    }
    
    return ans;  
}

int main()
{
    aa=read();bb=read();
    pre();
    printf("%d",work(bb+1)-work(aa));
    return 0;
}