DP

jinhaoxian @ 2018-08-02 22:11:12

by huangzhewer @ 2018-08-02 22:16:21

实在不行用记忆化搜索，DPn^4算法，，，转移方程呢

by jinhaoxian @ 2018-08-11 10:06:58

@huangzhewer 我太菜了，不知道什么是记忆化搜索，准备用BFS试试

by jinhaoxian @ 2018-08-11 10:17:44

结果WA七个点

by jinhaoxian @ 2018-08-11 10:19:38

改了一下变成40

by huangzhewer @ 2018-08-12 21:01:37

emm。。。。 我贴代码你理解一下，不要抄，照着思路自己写啊。。。

// luogu-judger-enable-o2
var
        k,l,i,j,n,m,ans:longint;
        a,x,y:array[0..10000] of longint;
        f:array[0..101,0..101] of longint;
        aa:array[0..101,0..101] of longint;

function max(n,m:longint):longint;
begin
        if n<m then exit(m)
        else exit(n);
end;

procedure kk(l,r:longint);
var
 i,j,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=a[(i+j) div 2];
        repeat
                while a[i]>mid do inc(i);
                while a[j]<mid do dec(j);
                if i<=j then
                begin
                        a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
                        x[0]:=x[i];x[i]:=x[j];x[j]:=x[0];
                        y[0]:=y[i];y[i]:=y[j];y[j]:=y[0];
                        inc(i);dec(j);
                end;
        until i>j;
        if i<r then kk(i,r);
        if j>l then kk(l,j);
end;

begin
        readln(n,m);
        for i:=1 to n do
        begin
                for j:=1 to m do
                begin
                        read(a[(i-1)*m+j]);
                        x[(i-1)*m+j]:=i;
                        y[(i-1)*m+j]:=j;
                        aa[i][j]:=a[(i-1)*m+j];
                end;
                readln;
        end;
        n:=n*m;
        kk(1,n);
        ans:=0;
        for i:=1 to n do
        begin
                k:=x[i];
                l:=y[i];
                if aa[k-1][l]>aa[k][l] then f[k][l]:=max(f[k][l],f[k-1][l]);
                if aa[k+1][l]>aa[k][l] then f[k][l]:=max(f[k][l],f[k+1][l]);
                if aa[k][l-1]>aa[k][l] then f[k][l]:=max(f[k][l],f[k][l-1]);
                if aa[k][l+1]>aa[k][l] then f[k][l]:=max(f[k][l],f[k][l+1]);
                inc(f[k][l]);
                if f[k][l]>ans then ans:=f[k][l];
        end;
        writeln(ans);
end.

by huangzhewer @ 2018-08-12 21:02:06

kk函数是快排。