giup doBARIC

const
fi='';
fo='';
nmax=101;
var f:text;
n,e,sl,tl: longint;
tg,kq,gt:array[0..nmax,0..nmax] of longint;
dau,cuoi: array[0..nmax] of longint;
m:array[0..nmax] of longint;

procedure input;
var i: longint;
begin
assign(f,fi);
reset(f);
readln(f,n,e);
for i:=1 to n do
readln(f,m[i]);
close(f);
end;

procedure tinh(i,j: longint; var tong: longint);
var tg1,k: longint;
begin
tg1:=m[i]+m[j] ;
for k:=i+1 to j-1 do
begin
tong:= tong+abs(tg1-2*m[k]);
if tong>e then
begin
tong:=e+1;
exit;
end;
end;
end;

procedure init;
var i,j,k: longint;
begin
fillchar(tg,sizeof(tg),0);
for i:=1 to n-2 do
for j:=i+2 to n do
tinh(i,j,tg[i,j]);
fillchar(dau,sizeof(dau),0);
fillchar(cuoi,sizeof(cuoi),0);
for i:=2 to n do
for j:=1 to i-1 do
begin
dau[i]:=dau[i]+ 2*abs(m[i]-m[j]);
if dau[i]>e then
begin
dau[i]:=e+1;
break;
end;
end;
for i:=n-1 downto 1 do
for j:=n downto i+1 do
begin
cuoi[i]:=cuoi[i]+2*abs(m[i]-m[j]);
if cuoi[i]>e then
begin
cuoi[i]:=e+1;
break;
end;
end;
end;

function min(x,y: longint): longint;
begin
min:=x;
if min>y then min:=y;
end;

procedure qhd;
var i,j,k: longint;
begin
sl:=0;
for i:=1 to n do
gt[1,i]:=dau[i];
for i:=1 to n do
if dau[i]+cuoi[i]<=e then
begin
sl:=1;
tl:=dau[i]+cuoi[i];
exit;
end;
{....................}
for i:=2 to n do
begin
gt[i,i]:=0;
for j:=i+1 to n do
begin
gt[i,j]:=e+1;
for k:=j-1 downto i-1 do
gt[i,j]:= min(gt[i,j],gt[i-1,k]+tg[k,j]);
end;
for j:=i to n do
if gt[i,j]+cuoi[j]<=e then
begin
sl:=i;
tl:=gt[i,j]+cuoi[j];
exit;
end;
end;
end;

procedure output;
begin
assign(f,fo);
rewrite(f);
writeln(f,sl,' ',tl);
close(f);
end;

begin
input;
init;
qhd;
output;
end.
http://vn.spoj.pl/problems/BARIC/
Nho xem ho xem bai nay sao chi duoc co 70/100

Bài này làm dài thế.
var
f,z: array [0..110,0..110] of longint;
a: array [0..110] of longint;
i,j,k,n,e: longint;
begin
read(n,e);
for i:=1 to n do read(a[i]);
for i:=1 to n+1 do
for j:=i-1 downto 0 do
begin
z[i,j]:=0;
if (i = n+1) and (j = 0) then z[i,j]:=e+1 else
for k:=j+1 to i-1 do
if i > n then inc(z[i,j],2*abs(a[k]-a[j])) else
if j < 1 then inc(z[i,j],2*abs(a[k]-a[i]))
else inc(z[i,j],abs(2*a[k]-a[i]-a[j]));
end;
for i:=0 to n+1 do
for j:=0 to n+1 do f[i,j]:=e+1;
f[0,0]:=0;
for i:=1 to n+1 do
for j:=1 to n+1 do
for k:=i-1 downto 0 do
if f[k,j-1]+z[i,k] < f[i,j] then
f[i,j]:=f[k,j-1]+z[i,k];
for k:=n+1 downto 0 do
if f[n+1,k] > e then
begin
writeln(k,' ',f[n+1,k+1]);
break;
end;
end.

Tư tưởng là QHD O(n^3) cộng tính toán trước. Bài ktuan cũng QHĐ vậy mà chỉ được 70, hơi lạ.

chao anh Nguyen Quang Anh cha cha kinh khung kinh khung