题目描述

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int N=15;
int f[N][N];

int dp(int n)
{
    //memset(f,0,sizeof f);
    if(n==0) return 1;
    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n=n/10;
    }
    int res=0;
    //last记录上一个数
    int last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=0;j<x;j++)
        {
            if(j==4 || (j==2)&&(last==6)) continue;
            res+=f[i+1][j];
        }
        //比如一个数是7621
        //break的时候，已经把76100-76199的给算完了，因为此时x=2，j就能到1
        if(x==4 || last==6 &&x==2) break;
        last=x;
        if(i==0) res++;

    }

    return res;
}

int main()
{
    for(int i=0;i<=9;i++)
    {
        if(i!=4)
        f[1][i]=1;
    }
    for(int i=2;i<N;i++)
    {
        for(int j=0;j<=9;j++)
        {
            if(j==4) continue;
            for(int k=0;k<=9;k++)
            {
                if(k==4 || (j==6)&&(k==2) ) continue;
                f[i][j]+=f[i-1][k];
            }
        }
    }

    int a,b;
    while(cin>>a>>b,a||b)
    {
        cout<<dp(b)-dp(a-1)<<endl;
    }
    return 0;
}

逐渐理解了数位dp，初始化f数组还是关键

这里提供了一种类似windy数不含前导0的做法
windy数不能直接在循环里第一位从0开始遍历的原因是 如0015其实是windy数，但如果不抛去前导0,01相邻就不是windy数了
这一题和数位之差没有关系，因此可以j从0开始遍历，如果不想要前导0的话可以特判一下首位从1开始，最后别忘了加上位数<num.size的情况

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

const int N=12;
int f[N][N];

int dp(int n)
{
    int res=0;
    int last=0;
    vector<int> num;

    while(n)
    {
        num.push_back(n%10);
        n=n/10;
    }
    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];
        if(i==num.size()-1)
        {
            for(int j=1;j<x;j++)
            {
                if(j!=4)
                res+=f[i+1][j];
            }
        }
        else
        {
            for(int j=0;j<x;j++)
            {
                if(j==4 || (last==6&&j==2)) continue;
                res+=f[i+1][j];
            }
        }
        if(last==6&&x==2 || x==4) break;
        last =x;
        if(i==0) res++;
    }
    for(int i=1;i<num.size();i++)
    {
        for(int j=1;j<=9;j++)
        {
            res+=f[i][j];
        }
    }
    return res;

}

int main()
{
    int a,b;
    for(int i=0;i<=9;i++)
    {
        if(i!=4)
        f[1][i]=1;
    }
    for(int i=2;i<=N-1;i++)
    {
        for(int j=0;j<=9;j++)
        {
            if(j!=4)
            for(int k=0;k<=9;k++)
            {
                if(j==6&&k==2 || k==4) continue;
                f[i][j]+=f[i-1][k];
            }
        }
    }

    while(cin>>a>>b,a||b)
    {
        cout<<dp(b)-dp(a-1)<<endl;
    }
    return 0;
}