第二部分thesum解题报告

1、Topcoder SRM 437 DiviTheSum解题I华东师范大学第二附属中学【时空限制】每个测试点时限 2 秒，空间限制无。【问题描述】给定三个正整数 A, B, C。支持三类操作：增加一个数字、修改一个数字、删除一个数字，各自有不同的代价Cost。求最小代价使 A+B=C，不允许前导零，不允许任一数为零。【数据规模和约定】A, B, C109;Cost106.【试题】如果不存在数 B，则问题转化为熟悉的“编辑距离”问题。从这个角度出发，可以认为这一题是推广的“编辑距离”问题。既然是推广的“编辑距离”问题，自然可以使用类似的状态设计和转移方法。用 fi, j, k, l表示 A 的后

2、i 位，B 的后 j 位，C 的后 k 位已经匹配完毕，进位为 l 的最小代价。转移时，可以从 fi+p, j+q, k+t, 0.1转移而来，其中 p, q, t 为 0 或 1 但不全为 0。每种转移可能都需要枚举新位上的数字，再根据情况计算代价。本题的关键在于摆脱枚举的惯性思维，抓住无后效性的特点进行动态规划。【算法描述】用 fi, j, k, l表示 A 的后 i 位，B 的后 j 位，C 的后 k 位已经匹配完毕，进位为 l 的最小代价。转移时，可以从 fi+p, j+q, k+t, 0.1转移而来，其中 p, q, t 为 0 或 1 但不全为 0。每种转移可能都需要枚举新位上的数

3、字，再根据情况计算代价。设 N=MaxlgA, lgB, lgC，则状态总数为 O(N3)。转移时需要考虑的状态为常数个，每个状态需要枚举的次数也为常数次。从而算法的总时间复杂度为 O(N3)，但有一个不小的隐含的常数因子。【其他算法】完成上述题解后，经过探索与交流，尚没有发现或了解本题的其他算法。【实现情况】实现情况【感谢】感谢 caoqinxiang 在其个人贴吧中提供的题解。【附录】原题Problem SementThere is nothing more beautifuln just aneger number.You are givenegers a, b and c. Write

4、 each of them down in decimal noion with no leading zeros. Thefollowing operations can be performed on each of the written numbers:Insert a single digianyition of the number (sibly at the beginning or at).Delete a single digit from the number.Replace a single digithe number with some other digit.An

5、operation can only be performed if it results in azeros.itive number wit least one digit and no leadingEach operation has an assoted cost - insCost, delCost and repCost, respectively. Return the minimals ble total cost of operations needed to satisfy the equality a+b=c.DefinitionClass:TheSumMethod:m

6、inCostParameters:,Returns:Method signature:minCost(a,b,c,insCost,delCost,repCost)(be sure your method is public)Constras- a, b, and c will each be betn 1 and 1,000,000,000, inclusive.- insCost, delCost and repCost will each be betn 0 and 1,000,000, inclusive.Exles0)447711111Returns: 1We just need to

7、 insert the digit 2 betn the two 1s.1)447711441Returns: 2This is the same situation as above, but with different costs. This time, the insert and delete operations aremuore expensive, and it is cher to make two replacements instead. For exle, we can turn thenumberso 44+17=61 for a total cost of 2.2)10010010000100000010000000Returns: 1000000Everys ble way requireseast one insert or delete operation.3)2345676519876927547301774498769977Returns: 48697This problem sement is the exclusive and proprietary property of TopCoder, Inc.Any unauthorized use or reproduc