资源描述：
《2000年第12届国际信息学奥赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2000年第12届国际信息学奥赛试题解析中国第一题回文词Day1.PalindromeTasktype:Batch.SourceoffilePalin*.TimeLimitperTestCase:6secondsPROBLEMApalindromeisasymmetricalstring,thatis,astringreadidenticallyfromlefttorightaswellasfromrighttoleft.Youaretowriteaprogramwhich,givenastring,determinestheminimalnumberofcharacterstobeins
2、ertedintothestringinordertoobtainapalindrome.Asanexample,byinserting2characters,thestring“Ab3bd”canbetransformedintoapalindrome(“dAb3bAd”or“Adb3bdA”).However,insertingfewerthan2charactersdoesnotproduceapalindrome.INPUTTheinputfilenameisPALIN.IN.Thefirstlinecontainsoneinteger:thelengthoftheinputstr
3、ingN,3≤N≤5000.ThesecondlinecontainsonestringwithlengthN.Thestringisformedfromuppercaselettersfrom‘A’to‘Z’,lowercaselettersfrom‘a’to‘z’anddigitsfrom‘0’to‘9’.Uppercaseandlowercaselettersaretobeconsidereddistinct.OUTPUTTheoutputfilenameisPALIN.OUT.Thefirstlinecontainsoneinteger,whichisthedesiredminim
4、alnumber.EXAMPLEINPUTANDOUTPUTPALIN.INPALIN.OUT25Ab3bd94参考译文：Day1回文词（题型：提交式；文件名：palin.*；时间限制：6s）问题描述：回文词是一种对称的字符串。也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是编写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如：字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。输入：输入文件的文
5、件名是palin.in。文件的第一行包含一个整数N，表示给定字符串的长度，3≤N≤5000。文件的第二行是一个长度为N的字符串。字符串仅由大写字母“A”到“Z”，小写字母“a”到“z”和数字“0”到“9”构成。大写字母和小写字母将被认为是不同的。输出：输出文件名是palin.out，文件只有一行，包含一个整数，表示需要插入的最少字符数。输入输出样例：Palin.inpalin.out25Ab3bd算法分析：本题可以采用动态规划方法来求解。令Gh[i,j]表示将原串S从第j位开始长度为i的子串s’变成回文词的最小添加字符数。按S’的长度大小依次进行递推求解：Gh[i,j]=94Gh[i–2,
6、j+1]若S[j]=S[i+j–1]，即首尾对称，1+Min{Gh[i–1,j],Gh[i–1,j+1]}若S[j]<>S[i+j–1]。2≤i≤n，1≤j≤n－i+1显然，当i=1或0时，Gh值均为0。为了节省空间，我们可以用两个一维数组滚动求解。参考程序如下。参考程序：{Pascal语言}programPalin;vars:array[1..5100]ofchar;n:integer;ans:integer;gh2,gh1,gh:array[1..5100]ofinteger;procedureini;varinf:text;i:integer;beginassign(inf,‘pal
7、in.in’);reset(inf);readln(inf,N);fillchar(s,sizeof(s),0);fori:=1toNdoread(inf,s[i]);close(inf);end;proceduremain;var94k,i:integer;beginfillchar(Gh2,sizeof(Gh2),0);fillchar(Gh1,sizeof(Gh1),0);fori:=1toN–1doifs[i]◇
