HỌC TIN CÙNG THỦ KHOA

Đề bài: Cho biểu thức a1•a2•…•an, trong đó ai là các số thực không âm và • là một phép toán + hoặc × cho trước. Hãy đặt các dấu ngoặc để biểu thức thu được có kết quả lớn nhất.

Mời các bạn download tại: Click here

const fi = 'BIEUTHUCSOHOC.INP';
      fo = 'BIEUTHUCSOHOC.OUT';
      MAXN = 100;

var  f:text;
     n: integer;
     a: array[1..MAXN] of real;
     L: array[1..MAXN, 1..MAXN] of real;
     H: array[1..MAXN, 1..MAXN] of integer;
     dau: array[1..MAXN] of char;

procedure Nhap;
var i:integer;
    s: string;
    so: string;
    len, k, code: integer;
begin
    assign(f, fi); reset(f);
    readln(f, s);
    s:= s + '$';
    len:= length(s);
    so:= '';
    k:= 0;
    for i:= 1 to len do
    begin
        if (s[i] = 'x') or (s[i] = '+') or (s[i] = '$') then
        begin
             inc(k);
             dau[k]:= s[i];
             val(so, a[k], code);
             so:= '';
        end
                else so:= so + s[i];
    end;
    n:= k;
    close(f);
end;

function max(a, b:real):real;
begin
    if a>b then exit(a) else exit(b);
end;

function TinhToan(a, b: real; dau: char): real;
begin
        if dau = 'x' then exit(a*b)
                else exit(a + b);
end;

procedure QHD;
var i, j, m, k: integer;
    tong: real;
begin
    for i:=1 to n do L[i, i] := a[i];
    for i:=1 to n-1 do L[i, i+1] := TinhToan(a[i], a[i+1], dau[i]);

    for m:=2 to n-1 do
        for i:=1 to n-m do
        begin
            j := i+m;
            L[i, j] := -1;
            for k:= i to j-1 do
            begin
                 tong:= TinhToan(L[i, k], L[k+1,j], dau[k]);
                 if L[i, j] < tong then
                 begin
                        L[i, j]:= tong;
                        H[i, j] := k;
                 end;
            end;
        end;
end;

function TruyVet(i, j:integer): string;
var k:integer;
    temp, temp2, s1, s2: string;
begin
        if i = j then
        begin
                str(a[i]:0:3, temp);
                exit(temp);
        end
        else if j = i + 1 then
        begin
                str(a[i]:0:3, temp);
                str(a[j]:0:3, temp2);
                exit('(' + temp + dau[i] + temp2 + ')');
        end
        else
        begin
                k:= H[i, j];
                s1:= TruyVet(i, k);
                s2:= TruyVet(k+1, j);
                exit('(' + s1 + dau[k] + s2 + ')');
        end;
end;


BEGIN
        Nhap;
        QHD;
        assign(f, fo); rewrite(f);
        writeln(f, L[1, n]:0:3);
        writeln(f, TruyVet(1, n));
        close(f);
END.