编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

还是不能秒杀。。。

var a:array[1..2500] of longint;

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

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

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

function f(k1,k2:longint):longint;

begin

f:=abs(x[k1]-x[k2])+abs(y[k1]-y[k2]);

f:=f*f;

end;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(k);

x[k]:=i;

y[k]:=j;

end;

readln;

end;

for i:=1 to n*n do

a[i]:=f(i,n*n);

for i:=n*n downto 1 do

begin

max:=0;

for j:=n*n downto i do

if f(i,j)+a[j]>max then max:=f(i,j)+a[j];

a[i]:=max;

end;

writeln(a[1]);

end.

写的(n*n)^2..我还当会超时...

DP真是神奇！- -

附lx贴网址那位的的思路：

（一）数据的存储

X(i),Y(i)分别表示高度为i的点的x、y坐标

（二）DP

BEST(i)=高度为i时的最大华丽度

（我喜欢用BEST()，不喜可改成f[]）

BEST(i)=max{BEST(i) , BEST(j)+dis(i,j)}

其中i+1≤y≤N^2

所以，所求的值为BEST(1)。

（三）C代码：（C语言有其优越性，就是看着舒服）

#include "stdio.h"

定义函数max(a,b)

定义函数exp(a) 返回a的平方

定义函数dis(i,j) 返回高度为i，j两点的华丽度

定义全局数组X[],Y[],BEST[]

int main()

{

//STEP #1

读入数组x[i]和Y[i]

//STEP #2

for(i=N*N;i>=1;i--)

for(j=i+1;j

原来如此

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

vag 6K过于强大?还是数据太水?

我可是用了n^2读入+n^2选排+n^2DP!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var i,j,n:longint;

a:array[0..53,0..53]of longint;

f,x,y,w:array[0..2603]of longint;

function max(x,y:longint):longint;

begin

if x>y then max:=x else max:=y;

end;

procedure qsort(l,r:longint);

var i,j,xx,t:longint;

begin

i:=l; j:=r; xx:=w[(i+j) div 2];

repeat

while w[i]>xx do inc(i);

while w[j]

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...　├ 标准行输出 1717...

　├ 错误行输出 2147...

├ 测试数据 07：答案错误...　├ 标准行输出 3943...

　├ 错误行输出 2147...

├ 测试数据 08：答案错误...　├ 标准行输出 4053...

　├ 错误行输出 2147...

├ 测试数据 09：答案错误...　├ 标准行输出 4015...

　├ 错误行输出 2147...

├ 测试数据 10：答案错误...　├ 标准行输出 4123...

　├ 错误行输出 2147...

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

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

const filename='p1474';

var

n,i,j,k:longint;

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

f:array[1..250000]of longint;

function max(x,y:longint):longint;

begin if x>y then exit(x);exit(y);end;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

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 downto 1 do

for j:=i+1 to n do

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

writeln(f[1]);

close(input);close(output);

end.

为什么这么做是不对的？

为什么没有秒杀！！！！！

水水的……

不过一开始差点当贪心了……

var

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

i,j,d,t,n: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;

for i:=2 to n*n do

for j:=1 to i-1 do

begin

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

if d+f[j]>f[i] then f[i]:=f[j]+d;

end;

writeln(f[n*n]);

end.

一开始悲剧了，把50*50＝250了，250..........

所以就有了40分的O^3的超时。

像“记忆化枚举”！！！！！

秒掉，咱来点C++

#include

using namespace std;

int i,j,n,it,mb,temp;

int x[2800],y[2800],num[2800];

void init()

{

cin >> n;

for(i=1;i it;

x[it]=i;

y[it]=j;

}

}

int main()

{

init();

num[n*n]=0;

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

{

mb=0;

for(j=i+1;jmb) mb=temp;

}

num[i]=mb;

}

cout

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

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

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

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

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(m);

g[m,1]:=i;

g[m,2]:=j;

end;

readln;

end;

max:=0;

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

begin

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

begin

m:=f[j]+sqr(abs(g-g[j,1])+abs(g-g[j,2]));

if f[i]max then

max:=f[i];

end;

writeln(f[1]);

end.

Flag 　　 Accepted

题号 　　P1474

类型(?) 　　动态规划

通过 　　1113人

提交 　　2245次

通过率 　　50%

难度 　　1

提交 讨论 题解

居然交两3次才AC,

50的平方居然是2500,,我真是个250...

第一次。。。

var

n:integer;

f:array[0..2500]of longint;

g:array[0..50,1..2]of integer;

procedure init;

var

i,j,k:integer;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(k);

g[k,1]:=i;

g[k,2]:=j;

end;

readln;

end;

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

end;

procedure work;

var

i,j:integer;

t:longint;

begin

for i:=n*n downto 1 do

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

begin

t:=f[j]+sqr(abs(g-g[j,1])+abs(g-g[j,2]));

if f[i]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

想自杀啊，数组开小了

悲哀...

n

5分钟搞定。。一遍AC。。可以说是那次比赛最水的一题了。。

最长不降子序列类似物。。

利用数组f记录i的位置，这样从n*n-1 downto 1 开始DP就可以满足无后效性，因为小的数字总是由大的数字转移而来的。。

这样的时间复杂度是O(n^4)，在n=50的情况下，应付所有的测试数据还是绰绰有余的~

以下贴出我的核心代码，仅供参考：

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

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

begin

if f[j,3]+sqr(abs(f[j,1]-f)+abs(f[j,2]-f))>f then

f:=f[j,3]+sqr(abs(f[j,1]-f)+abs(f[j,2]-f));

end;

不能用pow，否则输出结果是错的！！

痛打自己一百下。。。数组只开了0..50，囧。