自动搬运

查看原文

来自洛谷，原作者为

	青鸟_Blue_Bird 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:21:27，当前版本为作者最后更新于2020-05-04 00:06:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

博客园广告

这道题感觉是一个很另类的DP 至少我的做法是这样的。

重要前置思想：把A存成字符串！！！（应该也没人会想着存成int或者long long 吧）

首先，我们定义状态f[i][j]: 当我们处理A字符串到第i个位置时，我们还差j就能使式子的和等于B。

于是，开始想 手摸 状态方程。

嗯？怎么感觉有点难搞。 没事，慢慢来。

定义n = strlen(A), 即A字符串的长度, sum为剩下仍需要的数

首先看特殊情况：

如果i == n, 那么：

case1: sum < 0 ，很明显不符合要求，令f[n][sum] = INF;

case2: sum > 0, 同上，并不能满足等式成立，f[n][sum] = INF；

case3:sum = 0,符合我们的要求，令 f[n][sum] = 0;

那么，对于其余的情况，我们很容易有：

f[i][sum] = min{f[i + 1][num - A[position] | i <= position < n};

可是。这里要用到 i + 1啊，怎么实现？

递归呗！！

设计一个函数change，在递归过程中返回下一层（i + 1）层的值，同时修改f数组即可。

还没完！！ 注意到题目中的前置0了吗？ 如何处理这种情况呢？？

如此考虑：如果我们出现 " xx + 0 + xx"，这种情况肯定不是最优的，因为我们完全可以写成 " xx + 0xx" ,两边的式子大小一样，可是加号却被浪费了。于是，我们设定一个pre数组，作为循环时的起始点，作为对‘0’位置的特判。如果位置是0，我们则从其上一位（i + 1）开始循环，否则从他自己。

友情Tips：INF千万不要设成 ~0u >> 1、 2147483647等int上限，因为函数中有个地方要 + 1， 会超过上限。（我为此WA + RE了两遍）

细节标记在代码中了，没讲清楚的地方可以尝试着看看代码QAQ

上一波代码：

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9; /*千万不能写成int的极大值！！！下面会 + 1，造成错误*/
#define N 1010

char A[N]; 
int B; /*同题目*/
int pre[N], f[N][N * 5]; /*f是动规数组，pre为起始点（给 ‘0’用的）*/
int n; /*字符串的长度*/

int change(int now, int sum){
	if(now == n)return sum == 0 ? 0 : INF;
	int &cur = f[now][sum]; /*建个指针，懒得打那么长的 f数组*/
	if(cur != -1){
		return cur;
	}
	cur = INF;
	int temp = 0;
	for(int j = pre[now]; j < n; j++){
		temp = temp * 10 + A[j] - '0'; /*往上累加*/
		if(temp > sum) break;
		int hehe = change(j + 1, sum - temp);
		cur = cur < hehe + 1 ? cur : hehe + 1; 
	}
	return cur;
}

int solve(int now, int sum){ /*输出思路：一边输出A字符串，一边穿插 +号*/
	if(now == n){
		printf("=%d\n", B);
		return 1;
	}
	if(now > 0)printf("+");
	int num = 0;
	for(int j = now;j < n; j++){
		printf("%c", A[j]);
		num = num * 10 + A[j] - '0';/*有点快读那味儿了*/
		if(change(now, sum) == 1 + change( j + 1, sum - num)){
			return solve(j + 1, sum - num);
		}
	}
	return 0;
}

int main(){
	char c = getchar();
	while(isdigit(c)){
		A[n++] = c;
		c = getchar();
	}
	scanf("%d", &B);
	n = strlen(A);
	pre[n-1] = n - 1;
	for(int i = n - 2; i >= 0; i--){
		pre[i] = (A[i] == '0') ? pre[i + 1] : i;
	}
	memset(f, -1, sizeof(f)); /*初始化不要忘*/
	solve(0, B);
	return 0;
}