第二部分thesum解題報(bào)告

1、Topcoder SRM 437 DiviTheSum解題I華東師范大學(xué)第二附屬中學(xué)【時(shí)空限制】每個(gè)測(cè)試點(diǎn)時(shí)限 2 秒，空間限制無(wú)?！締?wèn)題描述】給定三個(gè)正整數(shù) A, B, C。支持三類(lèi)操作：增加一個(gè)數(shù)字、修改一個(gè)數(shù)字、刪除一個(gè)數(shù)字，各自有不同的代價(jià)Cost。求最小代價(jià)使 A+B=C，不允許前導(dǎo)零，不允許任一數(shù)為零?！緮?shù)據(jù)規(guī)模和約定】A, B, C109;Cost106.【試題】如果不存在數(shù) B，則問(wèn)題轉(zhuǎn)化為熟悉的“編輯距離”問(wèn)題。從這個(gè)角度出發(fā)，可以認(rèn)為這一題是推廣的“編輯距離”問(wèn)題。既然是推廣的“編輯距離”問(wèn)題，自然可以使用類(lèi)似的狀態(tài)設(shè)計(jì)和轉(zhuǎn)移方法。用 fi, j, k, l表示 A 的后

2、i 位，B 的后 j 位，C 的后 k 位已經(jīng)匹配完畢，進(jìn)位為 l 的最小代價(jià)。轉(zhuǎn)移時(shí)，可以從 fi+p, j+q, k+t, 0.1轉(zhuǎn)移而來(lái)，其中 p, q, t 為 0 或 1 但不全為 0。每種轉(zhuǎn)移可能都需要枚舉新位上的數(shù)字，再根據(jù)情況計(jì)算代價(jià)。本題的關(guān)鍵在于擺脫枚舉的慣性思維，抓住無(wú)后效性的特點(diǎn)進(jìn)行動(dòng)態(tài)規(guī)劃?！舅惴枋觥坑?fi, j, k, l表示 A 的后 i 位，B 的后 j 位，C 的后 k 位已經(jīng)匹配完畢，進(jìn)位為 l 的最小代價(jià)。轉(zhuǎn)移時(shí)，可以從 fi+p, j+q, k+t, 0.1轉(zhuǎn)移而來(lái)，其中 p, q, t 為 0 或 1 但不全為 0。每種轉(zhuǎn)移可能都需要枚舉新位上的數(shù)

3、字，再根據(jù)情況計(jì)算代價(jià)。設(shè) N=MaxlgA, lgB, lgC，則狀態(tài)總數(shù)為 O(N3)。轉(zhuǎn)移時(shí)需要考慮的狀態(tài)為常數(shù)個(gè)，每個(gè)狀態(tài)需要枚舉的次數(shù)也為常數(shù)次。從而算法的總時(shí)間復(fù)雜度為 O(N3)，但有一個(gè)不小的隱含的常數(shù)因子。【其他算法】完成上述題解后，經(jīng)過(guò)探索與交流，尚沒(méi)有發(fā)現(xiàn)或了解本題的其他算法?！緦?shí)現(xiàn)情況】實(shí)現(xiàn)情況【感謝】感謝 caoqinxiang 在其個(gè)人貼吧中提供的題解。【附錄】原題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