讨论 / 什么破玩意 -_-
wish 2009-03-25 20:48:00
点我顶贴 收藏 删除
http://www.rqnoj.cn/Status_Show.asp?SID=169882

郁闷。。。没有 Special Judge 就算了,后面10个点的诡异也就算了,可你到底不要搞这种阴人数据吧。。。

试问4(G)和GGGG有什么区别。。。。。。。

没空写题解,只上程序吧。。。虽然有点丢RP。。。

很简单的 2D/1D DP,只不过状态是字符串。每个状态要存储最短 FOLD 结果(程序里是 FF)和最短单位 FOLD(程序里 F 表示,Fold 为折叠次数)

program rq_275(input, output);

const

 maxN = 100;

 

var

 S, t: String;

 i, j, k, l, o: Longint;

 FF, F: array [1..maxN, 1..maxN] of String;

 Fold: array [1..maxN, 1..maxN] of Longint;

 

function IntToStr(u: Longint): String;

begin

 str(u, IntToStr)

end;

begin

 readln(S);

 for i := 1 to length(S) do

  begin

   F[i, i] := S[i];

   FF[i, i] := S[i];

   Fold[i, i] := 1

  end;

 for k := 1 to length(S) - 1 do

  for i := 1 to length(S) - k do

   begin

    j := i + k;

    FF[i, j] := copy(S, i, k + 1);

    Fold[i, j] := 1;

    F[i, j] := FF[i, j];

    for l := i + 1 to j do

     if F[i, l - 1] = F[l, j] then

      begin

       o := Fold[i, l - 1] + Fold[l, j];

       t := IntToStr(o);

       if length(F[l, j]) * o <= length(FF[i, j]) then

        begin

         Fold[i, j] := o;

         F[i, j] := F[l, j];

         if length(F[i, j]) + length(t) + 2 < length(FF[i, j]) then

          FF[i, j] := t + ’(’ + F[l, j] + ’)’

        end

      end

     else if length(FF[i, l - 1]) + length(FF[l, j]) < length(FF[i, j]) then

      begin

       F[i, j] := FF[i, l - 1] + FF[l, j];

       Fold[i, j] := 1;

       FF[i, j] := F[i, j]

      end

   end;

 writeln(FF[1, length(S)])

end.

查看更多回复
提交回复