题解：AT_ndpc2026_d 紙幣

manboo · 2026-05-07 09:48:13 · 题解

题意概述：

有纸币面额为 1,10,10^2,10^3,\dots,10^{100} 的纸币各无数张，设 f\left(x\right) 表示用以上纸币组合得出正整数 x 的最少纸币张数。T\left(1\le T\le10^4\right) 组测试数据，每次给你一个正整数 n\left(1\le n\le10^{18}\right)，求 \min\limits_{m\ge n}\left(f\left(m\right)+f\left(m-n\right)\right)。

啊嘞？为什么我看到这个题的第一眼就想暴搜啊？

对于一个数 x，其十进制下的最高位为 high，位数为 pos，则 f\left(x\right) 由以下三种情况转移过来：

• 用 high 张 10^{pos-1} 的纸币使 x 向下取整到第 pos 位，有 f\left(x\right)=high+f\left(x-high\times10^{pos-1}\right)。举例来说，f\left(8765\right)=8+f\left(8765-8000\right)。

• 用 high+1 张 10^{pos-1} 的纸币使 x 向上取整到第 pos 位，有 f\left(x\right)=high+1+f\left(\left(high+1\right)\times10^{pos-1}-x\right)。举例来说，f\left(8765\right)=9+f\left(9000-8765\right)。但是，由于可能会有 high=9 的情况，导致进位，此时应为 f\left(x\right)=1+f\left(10^{pos}-x\right)。举例来说，f\left(9876\right)=1+f\left(10000-9876\right)。

• 用 1 张 10^{pos} 的纸币使 x 向上取整到第 pos+1 位，当且仅当 10^{pos}-x<x，有 f\left(x\right)=1+f\left(10^{pos}-x\right)。举例来说，f\left(8765\right)=1+f\left(10000-8765\right)，但是不能让 f\left(10000-8765\right)=1+f\left(8765\right)。

那么只需要让 f\left(x\right) 等于以上三种的最小值即可。

很明显，直接暴搜会超时，考虑记忆化搜索，用 map 存储值 x 的 f\left(x\right)。

代码如下：

typedef long long ll;
ll pw[20];
map<ll,int> vis;
ll y;
int ans;
int dfs(ll x)
{
    if(vis.find(x)!=vis.end()) return vis[x];
    y=x;
    int high=0,pos=0;
    while(y) high=y%10,pos++,y/=10;
    ll a=x-high*pw[pos-1],b=(high+1)*pw[pos-1]-x,c=pw[pos]-x;
    int ans=min(high+dfs(a),(high==9?1:high+1)+dfs(b));
    return vis[x]=(c<x?min(ans,1+dfs(c)):ans);
}
int main()
{
    pw[0]=1;
    for(int i=1;i<=18;i++) pw[i]=pw[i-1]*10,vis[pw[i]]=1;
    vis[0]=0,vis[1]=1,vis[2]=vis[9]=2,vis[3]=vis[8]=3,vis[4]=vis[7]=4,vis[5]=vis[6]=5;
    for(int T=read();T;T--) print(dfs(read())),putchar('\n');
    return 0;
}