BZOJ4230: 倒计时

4230: 倒计时

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 20 Solved: 12
[Submit][Status][Discuss]

Description

这是一个特别的倒计时方法。

具体来说，一开始你有一个非负整数n。

每一次操作，你可以从当前的数上减去当前的数某个数位上的数值。当当前数变成0时，倒计时结束。

大概没什么人会对这样不便于使用的倒计时方法充满好奇，但是现在你仍然被要求回答让倒计时结束的最少操作次数。

Input

一行一个非负整数n

Output

让倒计时结束的最少操作次数

Sample Input

Sample Output

HINT

对于全部数据，n<=10^18

这就是郑远航眼中的NOIP题2333333

设f[x][len][y]为9999999y，共有len个9，前面最大值为x的数减到0以下的步数，g[x][len][y]为减到0以下剩的值。

然后对于x，我们先逐位减到0，然后就是秀智商与心理素质的时候了。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cmath>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i!=-1;i=next[i])

using namespace std;

typedef long long ll;

ll n,f[][][],g[][][],xp[];

int bit[],m;

int main() {

    rep(x,,) rep(y,,) {

        if(x<=y) f[x][][y]=,g[x][][y]=-x;

        else f[x][][y]=,g[x][][y]=-x+y;

    }

    xp[]=;

    rep(i,,) xp[i]=xp[i-]*;

    rep(len,,) rep(x,,) rep(y,,) {

        ll res=,cur=y;

        dwn(i,,) res+=f[max(i,x)][len-][cur],cur=g[max(i,x)][len-][cur];

        f[x][len][y]=res;g[x][len][y]=cur;

    }

    scanf("%lld",&n);

    if(!n) puts("");

    else if(n<) puts("");

    else {

        ll ans=,cur=n%,n0=n;

        while(n0) bit[++m]=n0%,n0/=;

        rep(i,,m-) {

            int C=;

            rep(j,i+,m) C=max(C,bit[j]);

            int k;

            if(i==) k=bit[i];

            else k=bit[i]-;

            dwn(j,k,) ans+=f[max(C,j)][i-][cur],cur=g[max(C,j)][i-][cur];

        }

        int k;

        if(m==) k=bit[m];

        else k=bit[m]-;

        dwn(i,k,) ans+=f[i][m-][cur],cur=g[i][m-][cur];

        dwn(i,m-,) dwn(j,,) ans+=f[j][i][cur],cur=g[j][i][cur];

        printf("%lld\n",ans+);

    }

    return ;

}

巴特西