windy数

windy数

参考：

题解 P2657 【[SCOI2009]windy数

windy数 数位dp练习题——只要学了数位dp就异常简单的题

用数位dp解决这个问题。

数位 DP 问题往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足 某种条件 的数的总数。

对于dp[i][j]：

表示具有i位数，且最高位为数字j的，满足题目条件的数的个数

递推求法：

void init()
{
    for(int i=0;i<=9;++i)
        dp[1][i]=1;
    for(int i=2;i<=11;++i)
        for(int j=0;j<=9;++j)
            for(int k=0;k<=9;++k)
                if(abs(j-k)>=2)               //题目条件
                    dp[i][j]+=dp[i-1][k];
}

对于最后的答案，我们设\(solve(x)\)，表示区间0~x内满足条件的数的总数。

求\(solve(x)\)，我们需要求三个部分。

①位数小于最大位数的部分

for(int i=1;i<cnt;++i)
  for(int j=1;j<=9;++j)
        ans+=dp[i][j];

②位数正好为最大位数但最高位不为边界值dig[cnt]的部分

for(int i=1;i<dig[cnt];++i)
    ans+=dp[cnt][i];

③逆向求数位边界部分，但是要注意最大数位，不能重复计算，即x这个值不可被多次计算，这就是第三行是<dig[i]而不是<=dig[i]的原因

for(int i=cnt-1;i>=1;--i)
    {
        for(int j=0;j<dig[i];++j)
            if(abs(j-dig[i+1])>=2)
                ans+=dp[i][j];
        if(abs(dig[i+1]-dig[i])<2) break;
        if(i==1) ans++;
    }

代码：

// Created by CAD on 2019/11/9.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[15][10];
void init()
{
    for(int i=0;i<=9;++i)
        dp[1][i]=1;
    for(int i=2;i<=11;++i)
        for(int j=0;j<=9;++j)
            for(int k=0;k<=9;++k)
                if(abs(j-k)>=2)
                    dp[i][j]+=dp[i-1][k];
}
ll solve(ll x)
{
    if(x<10) return x;
    int dig[15],cnt=0;
    while(x)
        dig[++cnt]=x%10,x/=10;
    ll ans=0;
    for(int i=1;i<cnt;++i)
        for(int j=1;j<=9;++j)
            ans+=dp[i][j];
    for(int i=1;i<dig[cnt];++i)
        ans+=dp[cnt][i];
    for(int i=cnt-1;i>=1;--i)
    {
        for(int j=0;j<dig[i];++j)
            if(abs(j-dig[i+1])>=2)
                ans+=dp[i][j];
        if(abs(dig[i+1]-dig[i])<2) break;
        if(i==1) ans++;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll l,r;
    cin>>l>>r;
    init();
    cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}