const

maxn=500;

dx:array[1..4] of integer=(-1,0,1,0);

dy:array[1..4] of integer=(0,1,0,-1);

var

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

i,j,k,t,max,r,c:longint;

function dfs(x,y:integer):integer;

var i,j,nx,ny,t:integer;

begin

if (xr)or(yc) then begin dfs:=0;exit;end;

if f[x,y]=0 then begin

for i:=1 to 4 do begin

nx:=x+dx[i];ny:=y+dy[i];

if (a[nx,ny]f[x,y] then f[x,y]:=t;

end;

end;

inc(f[x,y]);

end;

dfs:=f[x,y];

end;

begin

readln(r,c);

for i:=1 to r do

for j:=1 to c do read(a);

max:=0;

for i:=1 to r do

for j:=1 to c do begin

t:=dfs(i,j);

if t>max then max:=t;

end;

writeln(max);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用记忆化SO

瞬秒

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1011;

const o1:array[1..4] of integer=(0,0,-1,1);

o2:array[1..4] of integer=(-1,1,0,0);

var aa,dd:array[0..1000,0..1000] of longint;

n1,n2,i,j,k, big,fin:longint;

Procedure find(i,j,k:longint);

var h1,h2:Longint;

begin

if k>big then big:=k;

if k+aa-1>big then begin {-1 :k has up}

big:=k+aa-1;

exit;

end;

for h1:=1 to 4 do

if (dd[i+o1,j+o2 ]>=0) and (dd[i+o1,j+o2 ]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：30 有效耗时：3709ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这是第一次DP+QSORT 还是限定了深度才过的……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第二次记忆化搜索

我汗了…………

type

rec=record

x,y:longint;

end;

var

q:array[1..250000]of rec;

a:array[1..500,1..500]of longint;

f:array[1..500,1..500]of longint;

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

sum,k,max:longint;

procedure qsort(lx,rx:longint);

var

mid,i,j:longint;

t:rec;

begin

inc(times);if times>50 then begin exit; end;

i:=lx;j:=rx;mid:=a[q[i].x,q[i].y];

repeat

while a[q[i].x,q[i].y]mid do

dec(j);

if ij;

if ilx then qsort(lx,j);

dec(times);

end;

begin

readln(m,n);k:=0;

for i:=1 to m do

for j:=1 to n do

begin

read(a);

inc(k);

q[k].x:=i;q[k].y:=j;

end;

times:=0;

qsort(1,k);sum:=0;

for i:=1 to k do

begin

max:=0;

if (q[i].x+1a[q[i].x+1,q[i].y])

and(max=1)and(a[q[i].x,q[i].y]>a[q[i].x-1,q[i].y])

and(max=1)and(a[q[i].x,q[i].y]>a[q[i].x,q[i].y-1])

and(max

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

有点类似bellman_ford的思想与程序，就是时间有点---|---|

丑 - -|||

Flag 　　Accepted

题号 　　P1011

类型(?) 　　动态规划

通过 　　3545人

提交 　　15470次

通过率 　　23%

难度 　　2

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\_|

0 ms AC .. 记忆化DP。。思路绝对明确并且清晰。。

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\_|

const

v:array[1..4,1..2]of integer=((0,-1),(0,1),(1,0),(-1,0));

var

f:array[1..500,1..500]of longint;

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

m,n,ans:longint;

procedure init;

var i,j:longint;

begin

for i:=0 to 501 do

for j:=0 to 501 do a:=maxlongint;

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

readln(m,n);

for i:=1 to m do

begin

for j:=1 to n do read(a);

readln;

end;

ans:=0;

end;

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

var i,j,k:longint;

begin

if f[x,y]0 then exit(f[x,y]);

k:=0;

for i:=1 to 4 do

if a[x+v,y+v]k then k:=j;

end;

f[x,y]:=k+1;

exit(k+1);

end;

procedure work;

var i,j:longint;

begin

for i:=1 to m do

for j:=1 to n do

begin

if f=0 then f:=dp(i,j);

if f>ans then ans:=f;

end;

writeln(ans);

end;

begin

init;

work;

end.

就是合唱队形的变体!!!

把区域压成链，进行快排；

然后就是最长上升子序列了...

Program P1011(Input,Output);

Type

rec = record

h,p : longint;

end;

Var

max : longint;

r,c : longint;

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

g : array[1..500,1..500]of longint;

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

Procedure Init;

var

i,j : longint;

k : longint;

begin

readln(r,c);

for i := 1 to r do

begin

for j := 1 to c do

begin

k := (i-1)*c+j;

f[k].p := k;

read(f[k].h);

g := f[k].h;

end;

readln;

end;

max := 0;

for i := 1 to r*c do v[i] := 1;

end;

Procedure Sort(l,r : longint);

var

i,j,x : longint;

y : rec;

begin

i := l; j := r; x := f[(l+r) shr 1].h;

repeat

while f[i].h>x do inc(i);

while f[j].h=1 then k := f[i].p-c

else b := False;

4: if f[i].p+cf[i].h then

if v[k]+1>v[f[i].p] then v[f[i].p] := v[k]+1;

end;

end;

if v[f[i].p]>max then max := v[f[i].p];

end;

end;

BEGIN

Init;

Sort(1,r*c);

Calc;

writeln(max);

readln;

END.

他们写的都好乱＝ ＝

开始还用递推 结果这个题没有明确界限 用递推要转一维orz 所以用记忆化

const

dx:array[1..4]of longint=(-1,0,1,0);

dy:array[1..4]of longint=(0,1,0,-1);

//4个方向

var

n,m:longint;

map:array[0..501,0..501]of longint;

f:array[0..501,0..501]of longint;

function dp(i,j:longint):longint;

var

x,y,k:longint;

begin

if f1 then exit(f);

if (map[i+dx[1],j+dy[1]]>map)and(map[i+dx[2],j+dy[2]]>map)and(map[i+dx[3],j+dy[3]]>map)and(map[i+dx[4],j+dy[4]]>map) then exit(1);

//特殊情况 比四个方向都还低 返回1

for k:=1 to 4 do

begin

x:=i+dx[k];

y:=j+dy[k];

if (map[x,y]0) then

if f

Flag 　　Accepted

题号 　　P1011

类型(?) 　　动态规划

通过 　　3500人

提交 　　15306次

通过率 　　23%

难度 　　2

数据弱，把m打成n还能90分

3500个AC，赶上了

记忆搜ac

#include

#include

int a[502][502],dp[502][502];

int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};

int search(int r,int c){

int i,x,y,t;

if(dp[r][c]!=-1)return (dp[r][c]);

if(a[r][c]

program ski;

const

dx:array[1..4] of integer=(-1,0,0,1);

dy:array[1..4] of integer=(0,-1,1,0);

var

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

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

function work(s,t:longint):longint;

var

k,x,y,r:longint;

begin

if f0 then exit(f);

for k:=1 to 4 do

begin

x:=s+dx[k];

y:=t+dy[k];

if a>a[x,y] then

begin

r:=work(x,y);

if r>f then

f:=r;

end;

end;

inc(f);

exit(f);

end;

begin

assign(input,'ski.in');

reset(input);

assign(output,'ski.out');

rewrite(output);

fillchar(a,sizeof(a),0);

fillchar(f,sizeof(f),-1);

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

begin

read(a);

f:=0;

end;

readln;

end;

ans:=0;

for i:=1 to n do

for j:=1 to m do

begin

f:=work(i,j);

if f>ans then ans:=f;

end;

writeln(ans);

close(input);

close(output);

end.

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案错误...

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

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

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

记忆化搜索怎么会算错数呢？

大家要细心啊，用longint啊！！！

integer=90~~

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

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

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

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

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

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

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

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

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

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

type arr=record

num:longint;

i:longint;

j:longint;

end;

var a:array[0..2500] of arr;temp:arr;n,mm,i,j,max,xx:longint;

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

procedure work(l,m:longint);

var i1,j1:longint;

begin

i1:=l;j1:=i1*2;

while j1max then

max:=f[x];

end;

begin

read(n,mm);

for i:=1 to n do

for j:=1 to mm do

begin

read(xx);

a[(i-1)*mm+j].num:=xx;

a[(i-1)*mm+j].i:=i;

a[(i-1)*mm+j].j:=j;

end;

n:=n*mm;max:=-maxlongint;

for i:=n div 2 downto 1 do

work(i,n);

for i:=n downto 1 do

begin

temp:=a[1];

a[1]:=a[i];

a[i]:=temp;

work(1,i-1);

end;

for i:=1 to n do

f[i]:=search(i);

write(max);

end.

VJ不能用记录类型吗?郁闷

1次AC

dp到不变化

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

广东实验中学观光团到此一游

h的范围是真的吗？？？

小了吧......

害我交了五遍~~~

第一个点没过果然还是数组开小了，奇怪的是，我也是0..500怎么就不行呢?

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

快排+DP。。。求解第一个数据~

晕死排序排倒了还能过9个点。

数据水掉了