题解：AT_ndpc2026_d 紙幣
Wang_H_Y
·
·
题解
AT_ndpc2026_d 题解
思路
看到减法，想到小学学过的竖式计算。那么为了在这一位获得 d 的数字，可以直接得到 d 或是用上一位的 1 来当做 10 支付给他并收回 10-d 的回报。
我们定义 dp_{pos,op} 表示在数 n 上从低到高第 pos 位借位状态为 op 的最小钞票数量。
定义 $d$ 为数 $n$ 当前位的数字。
先考虑初始状态。$op=0$ 时就是 $0$ 因为 $0$ 元就用 $0$ 张钞票。$op=1$ 时由于一开始时遍历到的第一位是没有上一位的，所以不能从 $op=1$ 转移到第一位。考虑我们是取最小，因此赋极大值就可以。
考虑转移，分 $op=0$ 和 $op=1$ 转移。
$op=0$ 当前位需要花费 $d$ 的代价。考虑上一位如果从 $op=0$ 转移而来，那么上一位不会影响这一位。若从 $op=1$ 转移而来，则根据定义我们需要在这一位多加 $1$ 来保证上一位的借位是有效的。
$$
dp_{pos,0} = \min ({dp_{pos-1,0}+d,dp_{pos-1,1}+d+1})
$$
$op=1$ 时当前位根据定义要花费 $10-当前位原本代价$ 的代价，考虑原本代价就是 $op=0$ 时当前位 + 上一位的贡献，同样的分 $op=0$ 和 $op=1$ 考虑，也就是 $d$ 和 $d+1$。
$$
dp_{pos,1} = \min(dp_{pos-1,0}+(10-d),dp_{pos-1,1}+(10-(d+1)))
$$
从低到高的枚举每一位，做 dp，最后答案就是 $\min(dp_{n,0},dp_{n,1}+1)$。注意这里 $dp_{n,1}$ 要加 $1$ 因为在第 $n$ 位借位的话要在第 $n+1$ 位多付出一张钞票。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pii pair<int,int>
typedef long long ll;
inline ll read()
{
ll x=0,t=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-')
t=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*t;
}
inline void write(ll x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>=10) write(x/10);
putchar(x%10^48);
return ;
}
inline void write_L(ll x)
{
write(x);
putchar('\n');
}
inline void write_(ll x)
{
write(x);
putchar(' ');
}
void solve()
{
string n;
cin>>n;
int len=n.size();
n=' '+n;
ll dp0=0,dp1=1e18;
for(int i=len;i>=1;i--)
{
int d=n[i]-'0';
ll ndp0=min(dp0+d,dp1+d+1);
ll ndp1=min(dp0+(10-d),dp1+(10-(d+1)));
dp0=ndp0;
dp1=ndp1;
}
write_L(min(dp0,dp1+1));
}
int main ()
{
int T=read();
while(T--)
solve();
return 0;
}
```
考虑复杂度，由于对每一位做一次 dp，dp 一次是 $O(1)$ 的，总时间复杂度就是 $O(T|N|)$ 的。这里大概是 $2 \times 10^5$ 的操作次数。