自动搬运

查看原文

来自洛谷，原作者为

	___w **

搬运于2025-08-24 22:51:08，当前版本为作者最后更新于2023-12-16 11:25:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P9718 [EC Final 2022] Best Carry Player 2

进位这东西只能是从低位到高位考虑的吧，每位进不进位会影响下一位要填的数。

考虑数位 dp，从低位向高位填数字，设计状态 $f_{i,j,p}$ 表示当前第 $i$ 位，填完第 $i$ 个数字共进了 $j$ 位，当前这位是否有向前进 $1$，其中 $0$ 表示没有，$1$ 表示有。

这里设 $x$ 从右到左第 $i$ 位的值为 $a_i$，位权为 $w_i$（下标从 $1$ 开始编号）。

显然有

$$f_{i,j,0}=\min\begin{cases} f_{i-1,j,1} & a_i<9 \\ f_{i-1,j,0} \end{cases} $$$$f_{i,j,1}=\min\begin{cases} f_{i-1,j-1,1}+w_i(10-a_i-1) \\ f_{i-1,j-1,0}+w_i(10-a_i) & a_i>0 \end{cases} $$

但是这里题目要求的是正整数，不能为 $0$，但是注意到当答案为 $0$ 当且仅当 $k=0$，特判下就好了。

但是在写代码的时候被下面数据薄纱了

1
100000000000000000 18

原因是后面连续的 $0$ 不能提供进位，而且整个答案的长度就会变得很长，会爆 long long，因此我们只需把后面连续的 $0$ 去掉并最后加在答案上即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define ll long long
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : f, c = getchar();
	while (c >= '0' && c <= '9') x = (x<<3)+(x<<1)+(c^48), c = getchar();
	return x*f;
}

inline void write(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x/10);
	putchar('0'+x%10);
}

const int N = 20;
int lim = 19, a[N], w[N], f[N][N][2];

inline void upd(int &x, int y) { x = y < x ? y : x; }

inline void solve() {
	int x = read(), k = read(), cnt = 0;
	if (!k) {
		while (x%10 == 9) ++cnt, x /= 10;
		return (void)(write(w[cnt+1]), enter);
	}
	while (x%10 == 0) ++cnt, x /= 10;
	for (int i = 1; i <= lim; ++i) a[i] = x%10, x /= 10;
	memset(f, 0x3f, sizeof(f)), f[0][0][0] = 0;
	for (int i = 1; i <= lim; ++i)
		for (int j = 0; j <= k; ++j) {
			upd(f[i][j][0], f[i-1][j][0]);
			if (a[i] < 9) upd(f[i][j][0], f[i-1][j][1]);
			if (!j) continue;
			upd(f[i][j][1], f[i-1][j-1][1]+w[i]*(10-a[i]-1));
			if (a[i]) upd(f[i][j][1], f[i-1][j-1][0]+w[i]*(10-a[i]));
		}
	write(f[lim][k][0]);
	while (cnt--) write(0); enter;
}

signed main() {
	w[1] = 1;
	for (int i = 2; i <= lim; ++i) w[i] = w[i-1]*10;
	int t = read();
	while (t--) solve();
	return 0;
}