PROGRAM rabbit;

VAR

n,i,j,mi,mj,max,k:longint;

map,f:array[0..50,0..50]of longint;

FUNCTION sort(x,y:integer):longint;

var

t,i,j:longint;

begin

if (f[x,y]0)or(map[x,y]=1) then exit(f[x,y]);

for i:=1 to n do

for j:=1 to n do

if mapf[x,y] then

f[x,y]:=t;

end;

exit(f[x,y]);

end;

BEGIN

readln(n);

for i:=1 to n do

for j:=1 to n do

read(map);

for i:=1 to n do

for j:=1 to n do begin

if sort(i,j)>max then max:=sort(i,j);

end;

write(max);

END.

AC了...原来integer不够...

递推or记忆化

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：36ms

楼下的,你这样做似乎是因为题目所给的高度都是连续的,如果高度在LONint范围内,又不连续 那就暴空间 时间了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第180题...秒杀.

DP的LIS...

不用排序吧？直接下标记录高度

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program leimantu;

var

i,j,n,t,max:longint;

x,y,f:array[1..2500]of longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

begin

read(t);

x[t]:=i;

y[t]:=j;

end;

f[n*n]:=0;

for i:=n*n-1 downto 1 do

begin

max:=0;

for j:=i+1 to n*n do

begin

t:=f[j]+sqr(abs(x[j]-x[i])+abs(y[j]-y[i]));

if t>max then max:=t;

end;

f[i]:=max;

end;

writeln(f[1]);

end.

水题....哈哈^_^

不排序,直接DP.

編譯通過...

├ 測試數據 01：答案正确... 0ms

├ 測試數據 02：答案正确... 0ms

├ 測試數據 03：答案正确... 0ms

├ 測試數據 04：答案正确... 0ms

├ 測試數據 05：答案正确... 0ms

├ 測試數據 06：答案正确... 0ms

├ 測試數據 07：答案正确... 25ms

├ 測試數據 08：答案正确... 25ms

├ 測試數據 09：答案正确... 25ms

├ 測試數據 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗時：100ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

快排+N^2记忆化搜索 就好了

简单DP，轻松AC。

for i:=1 to n do

for j:=1 to n do

begin

read(a);

x[a]:=i;

y[a]:=j;

end;

f[x[n*n],y[n*n]]:=0;

for k:= n*n-1 downto 1 do

for i:= k+1 to n*n do

begin

f[x[k],y[k]]:=max(f[x[i],y[i]]+jump(x[k],y[k],x[i],y[i]),f[x[k],y[k]]);

end;

write(f[x[1],y[1]]);

简单 1次A

不过比赛时候用的别人的号 现在我都不知道自己成绩 ...

记录坐标,按高度排序,做一次N^2DP

F:=MAX(F[J]+DIST);

ANS:=F[N*N];

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program hly;

const cmax=50;

type zuobiao=record

x,y:longint;

end;

var

map:array[1..cmax,1..cmax] of longint;

zb:array[1..cmax*cmax] of zuobiao;

f:array[1..cmax*cmax] of longint;

n,ans:longint;

procedure init;

var

i,j:longint;

begin

readln(n);

fillchar(zb,sizeof(zb),0);

fillchar(f,sizeof(f),0);

for i:=1 to n do

for j:=1 to n do

begin

read(map);

zb[map].x:=i; zb[map].y:=j;

end;

ans:=0;

end;

procedure work;

var

i,j,max,v,id_zb:longint;

begin

f[n*n]:=0;

for i:=n*n-1 downto 1 do

begin

max:=0;

for j:=i+1 to n*n do

begin

v:=(abs(zb[j].x-zb[i].x)+abs(zb[j].y-zb[i].y))*(abs(zb[j].x-zb[i].x)+abs(zb[j].y-zb[i].y));

if f[j]+v>=max then begin max:=f[j]+v;id_zb:=j;end;

end;

f[i]:=f[i]+max;

end;

ans:=f[1];

writeln(ans);

end;

begin

init;

work;

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：100ms

比赛时只有90分。交同一条程序上去再测试。100分。全部0ms秒杀~无言

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：66ms

记忆化搜索

这个题和1012一样...

可我1012没过这道题却ac.

交了1题A1题，AC率100%，得分100.。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

qsort+DP

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

比赛时候不知道怎么回事^^^^^^开始号登不进了,又去注一个,结果就紧张了,第一题才20分

O(n^3)怎么做？

终于恶心过去了。。。。一开始用的O(n^3)的动规卡了6个点。。。。晕