楼下第二位,江湖骗子

看完题解才发现是真简单

本来准备用二维数组存储，这样有个排序问题 king465659的算法有点像计数排序（因为每个高度都出现且仅出现一次），这样就不用排序了

又有点小错:1. for i:=1 to n*n do 2.f[j,0]:=f+huali(i,j）应该往低的上面加 小心啊

color=red/color

另外，练一下记忆化搜索也好 也是秒杀

program rabbit;

var

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

f:array[1..2500] of qword;

i,j,m,n,x0,y0:integer;

k:longint;

ans:qword;

function hua(a,b:longint):longint;

begin

hua:=sqr(abs(x[a]-x)+abs(y[a]-y));

end;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do begin

read(k);

x[k]:=i;

y[k]:=j;

end;

n:=n*n;

for i:=n-1 downto 1 do begin

for j:=i+1 to n do

if f[i]+hua(i,j)+f[j]>ans then

ans:=f[i]+hua(i,j)+f[j];

f[i]:=ans;

end;

writeln(f[1]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC。

AC 标程，仅供参考。

谢谢。

program P1474;

var

n,i,j,k,l :longint;

ans :array[1..2500]of longint;

map :array[1..2500,1..2]of longint;

begin

fillchar(ans,sizeof(ans),0);

readln(n);

for i:=1 to n do

for j:=1 to n do

begin

read(k);

map[k,1]:=i; map[k,2]:=j;

end;

for i:=n*n downto 1 do

for j:=i-1 downto 1 do

begin

l:=ans[i]+sqr(abs(map-map[j,1])+abs(map-map[j,2]));

if l>ans[j] then ans[j]:=l;

end;

writeln(ans[1]);

end.

我的题解

本题可以使用动态规划以及记忆化搜索两种方法

1、动态规划

type node=record

x:longint;

i,j:shortint

end;

var

a:array[0..10000] of node;

b,f:array[1..10000] of longint;

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

procedure qsort(x,y:integer);

var

i,j,k:integer;

begin

i:=x;

j:=y;

k:=a[(x+y) div 2].x;

repeat

while a[j].xk do inc(i);

if ij;

if (j-x>0) then qsort(x,j);

if (y-i>0) then qsort(i,y);

end;

begin

readln(n);

k:=0;

for i:=1 to n do

for j:=1 to n do begin

inc(k);

read(a[k].x);

a[k].i:=i;

a[k].j:=j;

end;

qsort(1,k);

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

max:=0;

for i:=2 to n*n do begin

for j:=1 to i-1 do begin

if b[j]=0 then begin

t:=sqr(abs(a[i].i-a[j].i)+abs(a[i].j-a[j].j));

if f[i]max then max:=f[i];

end;

end;

end;

writeln(max);

end.

2、记忆化搜索

type node=record

x:longint;

i,j:shortint

end;

var

a:array[0..1000] of node;

b,f:array[1..1000] of integer;

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

procedure qsort(x,y:integer);

var

i,j,k:integer;

begin

i:=x;

j:=y;

k:=a[(x+y) div 2].x;

repeat

while a[j].xk do inc(i);

if ij;

if (j-x>0) then qsort(x,j);

if (y-i>0) then qsort(i,y);

end;

procedure dfs(x:integer);

var

i:integer;

begin

for i:=x+1 to n*n do begin

if b[i]1 then dfs(i);

t:=sqr(abs(a[x].i-a[i].i)+abs(a[x].j-a[i].j));

if f[x]

不错:

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

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

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

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

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

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

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

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

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

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

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

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

最长不下降序列

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

天...以后我数组一定有多大开多大...

RP问题啊...

比赛时PUPPY测秒杀

现在提交，

两次都是dolphin

第一次：

编译通过...

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

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

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

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

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

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

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

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

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

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：90 有效耗时：0ms

第二次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一样的程序

rp……验证码居然是xoxx……怪不得一次AC

我不想切水题，只是这题太水了，想不切都不行

滑雪是这个的加强版吧..

整形乘方用了POW就WA了……改了就AC了……

滑雪加强版（清帝之惑顺治）

打鼹鼠简化版……

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

最后输出错误~~白白丢了60分~偶哭~~~不然就进CSAPC的前50了~~~

一次AC..水题

f[i]表示从 i到n^2 的最大值

f[i]=max{f[j]+dis(i,j)} (j>i)

最后输出f[1]

for(i=n*n-1;i>0;i--)

{

max=0;

for(j=i+1;jmax)max=t+f[j];

}

f[i]=max;

}

printf("%ld",f[1]);