题解 P2188 【小Z的 k 紧凑数】

· · 题解

楼上题解好鬼畜。

数位dp模板题啊。

我们可以把答案拆成query(1,r)-query(1,l-1)。

那么我们只要求出1~x的这个区间的k紧凑数的数量就行了。

f[i][j]表示第i位上的数为j的k紧凑数的数量。

f[i][j]=\sum_{k=0}^{9}f[i-1][k] (|k-j|<=n)

对于统计就是先统计最高位比x小的方案数，然后再逐位统计。

例如query(1,432)=query(1,399)+query(400,429)+query(430,432)

然后把符合条件的加上就行了。

代码：

#include<cstdio>
#include<algorithm>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<cmath>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define cross(i,k) for (int i=first[k];i;i=last[i])
#define il inline
#define vd void
#define ll long long
using namespace std;
il ll read(){
    ll x=0;int ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
ll l,r,n,f[20][10],num[20],len;
//il int abss(int x){return x?x:-x;}
il vd dp(){
    For(i,0,9) f[1][i]=1;
    For(i,2,20)
        For(j,0,9)
            For(k,0,9)
                if (abs(j-k)<=n) f[i][j]+=f[i-1][k];
}
il ll query(ll x){
    len=0;
    For(i,0,20) num[i]=0;
    while (x>0){
        num[++len]=x%10;
        x/=10;
    }
    ll ans=0;
    For(i,1,len-1)
        For(j,1,9)
            ans+=f[i][j];
    Dow(i,len,1){
        For(j,0,num[i]-1){
            if (i==len&&!j) continue;
            if (abs(num[i+1]-j)<=n||i==len) ans+=f[i][j];
        }
        if (abs(num[i]-num[i+1])>n&&i!=len) break;
    }
    return ans;
}
int main(){
    l=read(),r=read(),n=read();
    dp();
    return printf("%lld",query(r+1)-query(l)),0;
}