P9718 [EC Final 2022] Best Carry Player 2

· · 题解

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;
}