P2657 windy数【数位dp】

· · 题解

数位dp模板题

数位dp一般解决的是一类数字问题：从l到r有多少个数符合某个性质，其中l和r都是很大的数，从l循环到r显然会TLE。

我们用f[i][j]表示搜到第i位，上一位数是j的情况下的方案总数

这道题我们可以处理1-(l-1)的方案数sum[l-1]和1-r的方案数sum[r]，则ans=sum[r]-sum[l-1]

接下来考虑怎么写转移

我们可以枚举每位上的0-9

特别地，如果前面的数取了能取的最大值或前面没有数字，那么这位上只能取到这位的最大数字

可能比较抽象，举个例子142857

142???

这时候第四位只能取到8，无法取到9 142857

141???

第3位没有取到最大值，所以第4可以取到9

最后我们考虑限制条件：相邻两位绝对值大于等于2

如果前一位是前导0，那么我们不需要考虑这位与0的绝对值，就是说0和1也是可以取到的

所以我们可以在处理下一位时把这位当做-2处理

下面是有详细注释的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15],ans;//dp[i][j]表示搜到第i位，前一位是j，的！limit方案totnum；
int a[15],len;
long long L,R;
ll dfs(int pos,int pre,int st,int limit)//pos当前位置,pre前一位数,st判断前面是否全是0,limit最高位限制 
{
    if(pos>len) return 1;//搜完了 
    if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];//没有最高位限制，已经搜过了
    ll ret=0;
    int res=limit?a[len-pos+1]:9;//当前位最大数字 
    for(int i=0;i<=res;i++)//从0枚举到最大数字 
    {
        if(abs(i-pre)<2) continue;//不符合题意，继续 
        if(st&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);//如果有前导0，下一位随意 
        else ret+=dfs(pos+1,i,0,limit&&i==res);//如果没有前导0，继续按部就班地搜 
    }
    if(!limit&&!st) dp[pos][pre]=ret;//没有最高位限制且没有前导0时记录结果 
    return ret;
}
void part(ll x)
{
    len=0;
    while(x) a[++len]=x%10,x/=10;
    memset(dp,-1,sizeof dp);
    ans=dfs(1,-2,1,1);
}
int main()
{
    scanf("%lld%lld",&L,&R);
    part(L-1);ll minn=ans;
    part(R);  ll maxx=ans;
    printf("%lld",maxx-minn);
    return 0;
}