简直神题啊。。。。我服气 我只会递推的数位DP啊，为啥题解都是dfs的
首先不难想到每次减少一定是变得越小越好，也就是找数位中最大的数减掉
可以这样想，每次把后面一段给压到00.....000x,然后在减去一个数变成999....999y
设f[mx][ln][u]为当前弄到第ln位，前面位的最大值为mx，最后面y等于u。u=10表示就是原数
直接这样转移好了
#include#include #include #include #include #include using namespace std;typedef long long LL;LL mi[20];int a[20];LL f[10][20][11];int res[10][20][11];void dfs(int mx,int ln,int u,LL n){ if(f[mx][ln][u]||res[mx][ln][u])return ; if(ln==1) { if(n==0||mx>n)f[mx][ln][u]=0,res[mx][ln][u]=n; else f[mx][ln][u]=1,res[mx][ln][u]=0; return ; } int tmx,tln=ln-1,tu=u;LL tn=n%mi[ln-1]; for(int i=(u==10)?a[ln]:9;i>=0;i--) { tmx=max(mx,i); dfs(tmx,tln,tu,tn); f[mx][ln][u]+=f[tmx][tln][tu]; tn=i*mi[ln-1]+res[tmx][tln][tu]; if(i!=0) { tu=10+res[tmx][tln][tu]-tmx; tn-=tmx;tn=tn%mi[ln-1]; f[mx][ln][u]++; } else res[mx][ln][u]=res[tmx][tln][tu]; }}int main(){ mi[0]=1;for(int i=1;i<=18;i++)mi[i]=mi[i-1]*10; LL n; scanf("%lld",&n); if(n==0){puts("0");return 0;} LL k=n,ln=0;while(k!=0)a[++ln]=k%10,k/=10; dfs(0,ln,10,n); printf("%lld\n",f[0][ln][10]); return 0;}