由于是连续的1～N^2，排序都免了。直接N^2的LIS即可

昨天的唯一一道水题，把矩阵拉成一维的，求最长不下降子序列即可

1次AC

program sun;

var

a:array[1..50,1..50] of integer;

c:array[1..2500,1..2] of integer;

b:array[1..50,1..50] of longint;

i,j,n,x,y,v,w:longint;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

begin

read(a);

c[a,1]:=i;

c[a,2]:=j;

end;

readln;

end;

fillchar(b,sizeof(b),0);

for i:=2 to n*n do

begin

x:=c;

y:=c;

b[x,y]:=0;

for j:=1 to i-1 do

begin

v:=c[j,1];

w:=c[j,2];

if sqr(abs(x-v)+abs(y-w))+b[v,w]>b[x,y]

then b[x,y]:=sqr(abs(x-v)+abs(y-w))+b[v,w]

end;

end;

write(b[c[n*n,1],c[n*n,2]]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀啊

邻接表超50%是不可能的，时间是一样的，你自己写会有问题吧

DIJ不可求最长路，因为你不知道最长的在哪里,但是取反后可以

SPFA可求，因为他是最优性剪枝+搜索

var i,j,n,ans,q:longint;

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

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

var k,t,tmp,l:longint;

begin

if f[x,y]>-1 then exit(f[x,y]);

t:=0;tmp:=0;

for k:=1 to n do

for l:=1 to n do

if a[k,l]t then t:=tmp;

end;

f[x,y]:=t;

exit(t);

end;

begin

read(n);

for i:=1 to n do

for j:=1 to n do

read(a);

for i:=1 to n do for j:=1 to n do f:=-1;

for i:=1 to n do

for j:=1 to n do

begin

q:=s(i,j);

f:=q;

if q>ans then ans:=q;

end;

write(ans);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

动规可也。比赛如是。

同学写了Dijkstra被灭掉了。事实证明dijk的贪心在求最长路时不成立。但是SPFA可以求最长路。

实验第一次，邻接表的SPFA，后5个竟然TLE……

实验第二次，邻接矩阵的SPFA，竟然全过……

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

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

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

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

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

实在是出乎意料。。。这个题邻接矩阵利用率是100%，但想不到比邻接表快那么多！

把SPFA的条件改为求最长路即可。

我又水了！！

当使用的floyed六组超时

后来O(N^2)就搞定了。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

水啊水啊水啊水……

O(N^2)

比赛时用了N^4的的DP，没了

n^2没秒。。。

用错算法，WA了一次

用了integer，又WA一次

天啊～

水题水题。。。

秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

太悲哀了，没有秒杀。。。。

冒泡（我比较懒）+DP的（n^4）算法，AC了，早知道编快排了

不过数据有点水啊，本来以为过不了的。。。

O(N^4) 的都能过,太假了.

数据做得太差了...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1474;

var

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

i,j,q,m,n:longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do begin

read(q);

a[q,1]:=i;

a[q,2]:=j;

a[q,0]:=0;

end;

for i:=sqr(n)-1 downto 1 do begin

for j:=sqr(n) downto i+1 do begin

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

if a

编译通过...

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

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

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

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

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

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

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

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

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

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

这是使用floyed算法求简单最长路的结果。供参考。

├ 测试数据 06：运行时错误...|错误号: -1073741819

├ 测试数据 07：运行时错误...|错误号: -1073741819

├ 测试数据 08：运行时错误...|错误号: -1073741819

├ 测试数据 09：运行时错误...|错误号: -1073741819

├ 测试数据 10：运行时错误...|错误号: -1073741819

为什么为什么？？？？

#include

static long n,x[1000],y[1000],p[1000];

main()

{

int i,j,ans=0,t;

scanf("%d",&n);

for(i=1;i

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

#include

#include

using namespace std;

struct node

{

int value,x,y;

};

node a[2600];

int b[2600]={0};

int dis(int x1,int y1,int x2,int y2);

void qs(int left,int right);

int part(int low,int high);

int main()

{

int n,i,j,k=0,s=0,maxx,bb;

cin>>n;

for(i=0;ia[k].value;

a[k].x=i;

a[k].y=j;

k++;

}

}

qs(0,n*n-1);

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

{

maxx=0;

for(j=i+1;jmaxx){maxx=bb;}

}

b[i]=maxx;

}

cout

第一次：O(N^6) 50分……

第二次 ： O(N^4)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

虽然没秒杀，但考试时怎么就没想到呢……-_-!