Bài 3: Pha hóa chất
Trước mặt Harry Poter có lọ hóa chất xếp thành một hàng. Mỗi lọ hóa chất có một màu trong số 100 màu đánh số từ 0 đến 99.
Harry muốn pha

Question

Bài 3: Pha hóa chất
Trước mặt Harry Poter có  lọ hóa chất xếp thành một hàng. Mỗi lọ hóa chất có một màu trong số 100 màu đánh số từ 0 đến 99.
Harry muốn pha  hóa chất trên thành một hóa chất duy nhất bằng cách trộn hai lọ đứng cạnh nhau trong dãy các lọ thành một lọ mới. Đặt lọ mới này vào vị trí mà hai lọ trước kia để lại.
Khi trộn hai hóa chất có màu  và  sẽ được một hóa chất mới có màu . Đồng thời, lượng khói bay ra là .
Hãy tìm lượng khói ít nhất bay ra khi Harry trộn  lọ hóa chất theo cách trên?
Dữ liệu: Vào từ file văn banrMIXTURES.INP. Dòng đầu tiên ghi  là số lượng bộ test (. Tiếp theo là  nhóm dòng, mỗi nhóm dòng mô tả một test có cấu trúc như sau:
Dòng đầu tiên ghi số nguyên dương ()
Dòng thứ hai ghi số nguyên nằm trong phạm vi [0...99] là màu của  lọ hóa chất.
Kết quả: Ghi ra file văn bản MIXTURES.OUT gồm  dòng mỗi dòng ghi kết quả của test tương ứng theo thứ tự.
Ví dụ
MIXTURES.INP
MIXTURES.OUT
 
2
2
18 19
3
40 60 20
342
2400
 Bài khó pascal

blsmath · Answer

var
  t,n,tam:int64;
  i,j,k,l:longint;
  a:array[1..100] of integer;
  b,c:array[1..1000,1..1000] of int64;
begin
  readln(t);
  while t>0 do
  begin
    dec(t); readln(n);
    for i:=1 to n do read(a[i]); readln;
    for i:=1 to n do (c[i,i], b[i,i]):=(a[i], 0);
    for l:=2 to n do for i:=1 to n-l+1 do
    begin
      j:=i+l-1; b[i,j]:=maxint; c[i,j]:=(c[i,j-1]+a[j]) mod 100;
      for k:=i to j-1 do b[i,j]:=min(b[i,j], b[i,k]+b[k+1,j]+c[i,k]*c[k+1,j]);
    end;
    writeln(b[1,n]);
  end;
end.

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group Dành Cho Lớp 8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

Bạn muốn hỏi điều gì?

Tìm kiếm với hình ảnh

Hãy đăng nhập hoặc tạo tài khoản miễn phí!

Lưu vào

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group Dành Cho Lớp 8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

Bạn muốn hỏi điều gì?

Lý do báo cáo vi phạm?