UOJ Logo Leo_h的博客

博客

Codeforces 331C The Great Julya Calendar

2017-01-17 20:29:59 By Leo_h

算是从文化课解脱出来以后第一道正经的题了 竟然没有题解,果断补一个

题目大意

输入正整数n(0<=n<=10^18),求每次减去一个数位上的数字,最少几次可以把n减成0

题解

看到数据范围就知道一定要按照数位讨论,但是取法都不知道怎么按数位看?因此考虑贪心 首先这里有个有趣的结论,最优解法一定是每次减去尽可能大的数字 证明:分别讨论最后一位是1~9亦或是0,结合数学归纳法可以得f(n)>=f(n-1)恒成立,因此f(n)是单调不递减的,也就是说更小的n一定对应相同或更小的步数,故对于已知的n要减去尽量大的数字 知道这个结论以后就可以按数位进行DP了(以下的n与上文的n完全不同) $DP[h][n][x]$表示还要考虑后n位,前面最大数字是h,后n位组成数字是x时,将x减到再减一次就需要向第n+1位借位时,所需的步数和减到的值 这时只需再减一次h就可以借位,使后n位变成999..9_这种数 考虑总状态数,h取0~9,n取1~18,但是x的取值范围是1~10^18?是不是会炸空间? 其实,在n已知的情况下,x仅可能取原数的一个后缀或者99...9加上一个数字,因此只有11种取值 这样之后,状态转移就很好写出了,详见代码 注意极限数据(0和1e18)!!

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define long long long
long tp[20];
struct ans
{
    long step;
    long rem;
    ans(){step=-1ll;}
    ans(long s,long r):step(s),rem(r){}
};
ans f[10][20][11];
ans query(int h,int n,long x)
{
    int xx=(x/10==tp[n-1]-1)?x%10:10;//whether x is 99...9_
    ans &key=f[h][n][xx];
    if(~key.step) return key;
    if(n==1) 
    {
        if (x>=h) return key=ans(1,0);
        else return key=ans(0,x); 
    }
    long cnt=0,cur=x%tp[n-1];
    int t=x/tp[n-1];
    while(t>=0)
    {
        ans tmp=query(max(h,t),n-1,cur);
        cnt+=tmp.step;
        cur=tmp.rem;
        if(t)
        {
            cur=cur+tp[n-1]-max(h,t);
            cnt++;
        }
        t--;
    }
    return key=ans(cnt,cur);
}
int main()
{
    tp[0]=1ll;
     for(int i=1;i<=18;i++) tp[i]=tp[i-1]*10ll;
     tp[19]=9000000000000000000ll;//!!!
     long n;
     int p=0;
     scanf("%I64d",&n);
    if(n==0)//!!!
    {
        printf("0");
        return 0;
    }
     while(tp[p]<=n) p++;
     ans tmp=query(0,p,n);
     printf("%I64d",tmp.step);
}
Leo_h Avatar