{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tLet \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\r\n\t\u003cp\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cul\u003e\r\n\t\t\u003cli\u003e\r\n\t\t\t\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\r\n\t\t\u003cli\u003e\r\n\t\t\t\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\r\n\t\t\u003cli\u003e\r\n\t\t\t\u003cb\u003eChange:\u003c/b\u003e letters at corresponding positions are distinct\u003c/li\u003e\r\n\t\u003c/ul\u003e\r\n\t\u003cp\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tCertainly, we would like to minimize the number of all possible operations.\u003c/p\u003e\r\n\t\u003cblockquote\u003e\r\n\t\t\u003cb\u003eIllustration\u003c/b\u003e\r\n\t\t\u003cp\u003e\r\n\t\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\t\u003cpre\u003e\r\n\t\t\u003ctt\u003eA G T A A G T * A G G C\r\n\r\n| | | | | | |\r\n\r\nA G T * C * T G A C G C\u003c/tt\u003e\u003c/pre\u003e\r\n\t\t\u003cp\u003e\r\n\t\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\t\u003cb\u003eDeletion:\u003c/b\u003e * in the bottom line\u003cbr /\u003e\r\n\t\t\u003cb\u003eInsertion:\u003c/b\u003e * in the top line\u003cbr /\u003e\r\n\t\t\u003cb\u003eChange:\u003c/b\u003e when the letters at the top and bottom are distinct\u003c/blockquote\u003e\r\n\t\u003cp\u003e\r\n\t\tThis tells us that to transform \u003ci\u003ex\u003c/i\u003e \u003d \u003cspan data-scayt_word\u003d\"AGTCTGACGC\" data-scaytid\u003d\"3\"\u003eAGTCTGACGC\u003c/span\u003e into \u003ci\u003ey\u003c/i\u003e \u003d \u003cspan data-scayt_word\u003d\"AGTAAGTAGGC\" data-scaytid\u003d\"4\"\u003eAGTAAGTAGGC\u003c/span\u003e 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\r\n\t\u003cp\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cpre\u003e\r\n\t\u003ctt\u003eA G T A A G T A G G C\r\n\r\n| | | | | | |\r\n\r\nA G T C T G * A C G C\u003c/tt\u003e\u003c/pre\u003e\r\n\t\u003cp\u003e\r\n\t\t\u0026nbsp;\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tand 4 moves would be required (3 changes and 1 deletion).\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tIn 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 \u0026ge; \u003ci\u003em\u003c/i\u003e.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tAssign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tWrite 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\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tThe 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\r\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tAn 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\r\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n10 \u003cspan data-scayt_word\u003d\"AGTCTGACGC\" data-scaytid\u003d\"1\"\u003eAGTCTGACGC\u003c/span\u003e\r\n11 \u003cspan data-scayt_word\u003d\"AGTAAGTAGGC\" data-scaytid\u003d\"2\"\u003eAGTAAGTAGGC\u003c/span\u003e\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n4\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t参考课本6.3节\u003c/p\u003e"}}]}