Question

c++动态规划题目

题目描述
有三个整数A、B、C，1 ≤ A ≤ 10^1000，1 ≤ B ≤ 10^1000，1 ≤ C ≤ 10^1000），如何改变A、B、C的某些位，使得A+B=C？改变一个数的某位的代价，为该位改变前后数字的差的绝对值。最终的代价为所有位的代价之和。你不能使三个数中的任一个减少位数（使最高位变0），也不能增加位数（在最高位前增加若干位）。
输入
第一行一个整数A（ 1 ≤ A ≤ 10^1000），第二行一个整数B（ 1 ≤ B ≤ 10^1000），第三行一个整数C（ 1 ≤ C ≤ 10^1000）。
输出
一个整数，表示最小代价。如果无论怎样改变，A+B都不能等于C，则输出“-1”。
样例输入
123
554
345
样例输出
8
【样例说明】

可以将A变为121，代价2，将B变为324，

代价5，将C变为445，代价1，总代价为8。

Answer 1

从个位开始考虑，每一位有下列情况：进位或不进位，上一位进位或不进位。由于个位无需考虑上一位的进位问题，故只有两种确定情况，而高位的数值则会受到低位数值进位的影响，故可设计一个2*n的数组，由于存放每一位上进位和不进位两种情况下从个位开始代价的总和。从个位开始向最高位计算，分别求出在上一位进位或不进位的情况，并通过数组中已有的上一位数据计算该位的最小代价。