算法课设

圈乘运算问题

问题描述

定义 \(X@Y\) = 十进制整数 \(X\) 的各位数字之和 * 十进制整数 \(Y\) 的最大数字 + \(Y\) 的最小数字

对于给定的 \(X, K\) ，计算出由 \(X, @\) 组成的表达式值为 \(K\) 的表达式最少需要多少个 \(@\) 运算

算法设计

容易得放缩式 \[ \displaylines{X@Y \le 81 \times N + 9\\ where:\ N -1 < lg(X) \le N} \] 此式是容易证明的

注意到 \(N\) 代表着 \(X\) 的位数，则显然有十进制整数 \(X\) 的各位数字之和小于 \(9N\) ，又十进制中每一位最大值为 \(9\) ，故上式得证。

当取最小位为 \(0\) ,最大位为 \(1\) 时，同理可证明其下界为

\[ X@Y \ge X \]

定义 \(g(X,\ K)\) 为计算最小 \(@\) 数量的函数，\(G[i]=g(X, i)\) 则可得其状态转移方程为

\[ \displaylines{G[i+j]=min\{G[i+j],\ G[i]+G[j]+1\}\\ where:\ X \le i,j \le K} \] 综上，参考cpp代码如下

#include <algorithm>
#include <cstring>
#include <iostream>

#define i32 int
#define i64 long long
#define u128 unsigned long long
#define u32 unsigned int

using namespace std;
const i32 MAXN = (int) 5e2;
// const i64 M = 1e10;
const auto L = 0x3f;

i64 G[MAXN];
i64 X, K;

i64 f (i64 X, i64 Y) {//X@Y运算
    i64 numX = 0, mxY = 0, mnY = 10;
    while (X) {
        numX += X % 10;
        X /= 10;
    }
    while (Y != 0) {
        mxY = max (mxY, Y % 10);
        mnY = min (mnY, Y % 10);
        Y /= 10;
    }
    return numX * mxY + mnY;
}

i64 get_lim (i64 X, i64 K) {//获取上界
    auto num = 0;
    while (X) {
        X /= 10;
        num++;
    }
    i64 lim = max (num, 2) * 81 + 9;
    return max(lim, K);
}


int main () {
    memset (G, L, sizeof (G));
    cin >> X >> K;
    auto lim = get_lim (X, K);
    G[f (X, X)] = 1;
    G[X] = 0;

    if (X > K) {
        goto error;
    }


    for (auto i = X; i <= lim; ++i) {
        for (auto j = X; j <= lim; ++j) {
            if (G[i] < L && G[j] < L && G[f (i, j)] > G[i] + G[j] + 1) {//i@j到S的运算次数更少,则更新
                G[f (i, j)] = G[i] + G[j] + 1;
            }
        }
    }

    if (G[K] < L) {
        cout << G[K] << endl;
        // for (auto p = X; p <= K; ++p) {
        //     cout << p << ":" << G[p] << " ";
        // }
        // cout << endl;
    }
    else {
    error:
        cout << "error" << endl;
    }
    return 0;
}