题解 P6509 【[CRCI2007-2008] JEDNAKOST】

[博客园广告](https://www.cnblogs.com/wondering-world/p/12824895.html) 这道题感觉是一个很另类的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 上一波代码： ```cpp #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; } ```