折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S @ S

                        2. X(S)是X(X>1)个S 连接在一起的串的折叠。记作X(S)即SSSS…S(X 个S)。

                        3. 如果A @ A’, B @ B’，则AB @ A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) @ AAACBB，

                            而2(3(A)C)2(B) @AAACAAACBB

                       给一个字符串， 求它的最短折叠。

一道DP题目，考试的时候在折叠时的转移搞乱了——

用f[i,j]表示从i到j折叠后的最短长度，那么f[i,j]=min{f[i,k]+f[k+1,j]  x<=k<y

                                                                    f[i,k]+2+length((y-x+1) div (k-i+1))  s(i,k)是s(i,j)的一个折叠单位}

记忆化搜索较好实现，我的搜索过程中写的字符串变量，节点多时会run time error，但结果一定正确，只要字符串尽量开在外面就行了，领会精神。

1 program zd(input,output);  2 var  3    s   : ansistring;  4    f   : array[0..101,0..101] of longint;  5 procedure init;  6 var  7    i,j : longint;  8 begin  9    readln(s); 10    for i:=1 to length(s) do 11       for j:=1 to length(s) do 12      if i=j then 13         f[i,j]:=1 14      else 15         f[i,j]:=-1; 16 end; {
      init } 17 function try(ss    : ansistring; s1:ansistring ):boolean; 18 begin 19    try:=true; 20    while ss<>'' do 21    begin 22       if pos(s1,ss)=1 then 23      delete(ss,1,length(s1)) 24       else 25      exit(false); 26    end; 27 end; {
      try } 28 function min(aa,bb: longint ):longint; 29 begin 30    if aa
      
       -1 then 40       exit(f[x,y]); 41    f[x,y]:=y-x+1; 42    for k:=x to y-1 do 43    begin 44       tmp:=dfs(x,k)+dfs(k+1,y); 45       if tmp
       
        >1) do 50       if (length(s1) mod (k-x+1)=0) then 51       begin 52      s2:=copy(s,x,k-x+1); 53      if try(s1,s2) then 54      begin 55         tmp:=dfs(x,k); 56         str(length(s1) div (k-x+1),s3); 57         if tmp+2+length(s3)