{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eLet \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e be two strings over some finite alphabet \u003ci\u003eA\u003c/i\u003e. We would like to transform \u003ci\u003ex\u003c/i\u003e into \u003ci\u003ey\u003c/i\u003e allowing only operations given below:\u003c/p\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003e\u003cb\u003eDeletion:\u003c/b\u003e a letter in \u003ci\u003ex\u003c/i\u003e is missing in \u003ci\u003ey\u003c/i\u003e at a corresponding position.\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eInsertion:\u003c/b\u003e a letter in \u003ci\u003ey\u003c/i\u003e is missing in \u003ci\u003ex\u003c/i\u003e at a corresponding position.\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eChange:\u003c/b\u003e letters at corresponding positions are distinct\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cp\u003eCertainly, we would like to minimize the number of all possible operations.\u003c/p\u003e\n \u003cblockquote\u003e\n \u003cb\u003eIllustration\u003c/b\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cpre\u003e\u003ctt\u003eA G T A A G T * A G G C\n\u003cbr\u003e| | | | | | |\n\u003cbr\u003eA G T * C * T G A C G C\u003c/tt\u003e\u003c/pre\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cb\u003eDeletion:\u003c/b\u003e * in the bottom line\n \u003cbr\u003e\n \u003cb\u003eInsertion:\u003c/b\u003e * in the top line\n \u003cbr\u003e\n \u003cb\u003eChange:\u003c/b\u003e when the letters at the top and bottom are distinct\n \u003c/blockquote\u003e\n \u003cp\u003eThis tells us that to transform \u003ci\u003ex\u003c/i\u003e \u003d AGTCTGACGC into \u003ci\u003ey\u003c/i\u003e \u003d AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like\u003c/p\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cpre\u003e\u003ctt\u003eA G T A A G T A G G C\n\u003cbr\u003e| | | | | | |\n\u003cbr\u003eA G T C T G * A C G C\u003c/tt\u003e\u003c/pre\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cp\u003eand 4 moves would be required (3 changes and 1 deletion).\u003c/p\u003e\n \u003cp\u003eIn this problem we would always consider strings \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e to be fixed, such that the number of letters in \u003ci\u003ex\u003c/i\u003e is \u003ci\u003em\u003c/i\u003e and the number of letters in \u003ci\u003ey\u003c/i\u003e is \u003ci\u003en\u003c/i\u003e where \u003ci\u003en\u003c/i\u003e ≥ \u003ci\u003em\u003c/i\u003e.\u003c/p\u003e\n \u003cp\u003eAssign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.\u003c/p\u003e\n \u003cp\u003eWrite a program that would minimize the number of possible operations to transform any string \u003ci\u003ex\u003c/i\u003e into a string \u003ci\u003ey\u003c/i\u003e.\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eThe input consists of the strings \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e prefixed by their respective lengths, which are within 1000.\u003c/p\u003e\n多组输入输出\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eAn integer representing the minimum number of possible operations to transform any string \u003ci\u003ex\u003c/i\u003e into a string \u003ci\u003ey\u003c/i\u003e.\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e10 AGTCTGACGC\n11 AGTAAGTAGGC\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4\u003c/pre\u003e"}}]}