- 矩阵取数游戏
- 2009-08-11 15:51:31 @
各位大牛。。。
这道题我是用最朴素的算法...
f表示左边开始取了i次.右边开始取了j次的最大值....
f:=max(f+a[i]*2^(i+j),f+a[j]*2^(i+j))
为什么我会错了啊?!?!????
const
maxm=81;
maxn=50;
mk=1000000;
type
sty=array[0..maxn] of longint;
var
ans:sty;
pdf:int64;
n,m:longint;
i,j,k,t:longint;
twice:array[0..maxm] of sty;
data:array[0..maxm] of longint;
f:array[-1..maxm,-1..maxm] of sty;
procedure print;
var
s:string;
i,j,k:longint;
begin
if ans[0]=1 then writeln(ans[1]) else begin
write(ans[ans[0]]);
for i:=ans[0]-1 downto 1 do begin
str(ans[i],s);
for j:=1 to (6-length(s)) do write('0');
write(ans[i]);
end;
end;
close(input);
close(output);
end;
function mak(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
function max(x,y:sty):sty;
var
flag:boolean;
i,j,k:longint;
begin
if x[0]>y[0] then exit(x);
if y[0]>x[0] then exit(y);
flag:=true;
for i:=x[0] downto 1 do if y[i]>x[i] then begin
flag:=false;
break;
end;
if flag then exit(x)
else exit(y);
end;
procedure inq(x:sty;var y:sty);
var
c:sty;
len:longint;
i,j,k:longint;
begin
k:=0;
len:=mak(x[0],y[0]);
fillchar(c,sizeof(c),0);
for i:=1 to len do begin
c[i]:=(x[i]+y[i]+k) mod mk;
k:=(x[i]+y[i]+k) div mk;
end;
c[0]:=len;
if k>0 then begin
inc(c[0]);
c[c[0]]:=k;
end;
y:=c;
end;
procedure prem(x,y:longint;var z:sty);
var
i,j,k:longint;
begin
fillchar(z,sizeof(z),0);
for i:=1 to twice[y,0] do begin
pdf:=twice[y,i]*x+z[i];
z[i]:=pdf mod mk;
z:=pdf div mk;
end;
z[0]:=twice[y,0];
if z[z[0]+1]0 then inc(z[0]);
while (z[z[0]]=0)and(z[0]0) do dec(z[0]);
end;
procedure refil;
var
i,j,k:longint;
begin
twice[0,0]:=1;
twice[0,1]:=1;
for i:=1 to maxm do begin
k:=0;
twice:=twice;
for j:=1 to twice do begin
twice:=(twice*2+k) mod mk;
k:=(twice*2+k) div mk;
end;
if k0 then begin
inc(twice);
twice[i,twice]:=k;
end;
end;
end;
procedure work;
var
a,b,tot:sty;
begin
refil;
for t:=1 to n do begin
fillchar(tot,sizeof(tot),0);
for i:=1 to m do read(data[i]);
for i:=0 to m do begin
for j:=0 to m do begin
if i+j>m then break;
prem(data[i],i+j,a);
prem(data[m-j+1],i+j,b);
inq(f,a);
inq(f,b);
f:=max(a,b);
end;
end;
for i:=0 to m do tot:=max(tot,f);
inq(tot,ans);
readln;
end;
end;
procedure init;
begin
assign(input,'game.in');
reset(input);
assign(output,'game.out');
rewrite(output);
readln(n,m);
end;
begin
init;
work;
print;
end.