郁闷。。。没有 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.