洛谷P6509 [CRCI2007-2008] JEDNAKOST 题解

题目链接：洛谷P6509 [CRCI2007-2008] JEDNAKOST

题意：

给定一个形如 A=B 的字符串，其中 \(A\) 和 \(B\) 都是不含前导零的正整数。请给 \(A\) 的一些相邻数位之间加上加号，要求添加的加号数量最少，使得等式成立。

在 \(A\) 加上加号后，每个加数允许有多个前导 \(0\)。包括 \(0\) 在内。也即允许形如 \(000 \ldots\) 的数作为加数。

数据保证有解。

输入格式：

输入只有一行一个形如 A=B 字符串，表示给定的等式。

输出格式：

本题存在 Special Judge。

输出一行一个字符串，表示加上加号以后的成立的等式。

数据范围：

保证 \(1 \leq A \lt 10^{1000}\)，\(1 \leq B \leq 5 \times 10^3\)，\(A \neq B\)。

看上去只有 dfs 能解，因此考虑记忆化搜索。

设 \(f(i,j)\) 表示走到 \(i\) ，还差 \(j\) 就能使式子的和等于 \(B\) ，则 \[ \begin{aligned} f(i,j) \downarrow f(k,j - \operatorname{Num}[\mathrm{pre}(i)..k]) && k \ge \mathrm{pre}(i) \end{aligned} \] 其中 \[ \begin{aligned} \mathrm{pre}(i) = \begin{cases} n - 1 & i = n-1 \\[6pt]i & i \ne n-1\land A_i \ne 0 \\[6pt] \mathrm{pre}(i+1) & i \ne n-1\land A_i = 0 \end{cases} && (0\le i\le n-1) \end{aligned} \] 用于特判前导零。其原理可以考虑 xx+0+xx 和 xx+0xx ，显然后者更优。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

string A; int n,B,pre[N],f[N][N * 5];
int dfs(int now,int sum)
{
    if(now == n) return sum == 0 ? 0 : INF;
    int &cur = f[now][sum]; if(cur != -1) return cur;
    cur = INF; int tmp = 0;
    for(int j = pre[now]; j < n; j++)
    {
        tmp = tmp * 10 + A[j] - '0'; if(tmp > sum) break;
        down(cur, dfs(j + 1, sum - tmp) + 1);
    }
    return cur;
}
bool solve(int now,int sum)
{
    if(now == n) { cout << '=' << B << '\n'; return true; }
    else if(now > 0) { cout << '+'; }
    int num = 0;
    for(int j = now; j < n; j++)
    {
        cout << A[j]; num = num * 10 + A[j] - '0';
        if(dfs(now, sum) == 1 + dfs(j + 1, sum - num)) {
            return solve(j + 1, sum - num);
        }
    }
    return false;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> A; int pos = A.find_first_of('=');
    B = stoi(A.substr(pos + 1)); A.erase(pos); n = A.size();
    pre[n - 1] = n - 1;
    for(int i = n - 2; ~i; i--) {
        pre[i] = (A[i] == '0') ? pre[i + 1] : i;
    }
    memset(f, -1, sizeof(f)); solve(0, B);
    return 0;
}

---

参考文献：

[1] https://you-can-do-it.blog.luogu.org/solution-p6509