改了又改，也就改成这样了，有很多弄复杂的地方，请大牛们指教……

var

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

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

n,m,i,j,k,num,num1:longint;

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

begin

if x>y then max:=x

else max:=y;

end;

begin

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

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

readln(m,n);

for i:=1 to m do

for j:=1 to n do

read(a[j,i]);

for k:=1 to m+n-2 do

for i:=1 to n do

for j:=1 to n do

if (ij)or((i=n)and(j=n)) then

if ((k+2-i>0)and(k+2-j>0)and(k+2-i

NOIP2008的题另人神伤。。。

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

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

此题用一个四维数组五重循环就可以过了

但最好学一下 用三维数组三重循环的DP

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

此题可看成 从(1，1)到(m,n)两条不相交的路线（除起点到终点外）

每走一步两条路线都会在相应的对角线上 由对角线来DP

—————————————

dp:=max(dp,

dp(j

题很经典，具体我就不讲了，希望广大的dp初学者认真品味此题。我只想提醒大家要注意边界条件（很多）。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：60 有效耗时：212ms

万恶的6K, 我在我机子上过 总共也就0.3s

编译通过...

├ 测试数据 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

#include

FILE *fin,*fout;

int a[51][51]={0},m,n,f[51][51][51][51]={0};

int try(int i1,int j1,int i2,int j2)

{int max,x;

if(i1==0||j1==0||i2==0||j2==0) return 0;

else if(i1==i2&&j1==j2&&i1!=m) return -1;

else

{max=try(i1-1,j1,i2-1,j2);if(max!=-1)max+=a[i1-1][j1]+a[i2-1][j2];

x=try(i1-1,j1,i2,j2-1);if(x!=-1)x+=a[i1-1][j1]+a[i2][j2-1];if(x>max) max=x;

x=try(i1,j1-1,i2,j2-1);if(x!=-1)x+=a[i1][j1-1]+a[i2][j2-1];if(x>max) max=x;

x=try(i1,j1-1,i2-1,j2);if(x!=-1)x+=a[i1][j1-1]+a[i2-1][j2];if(x>max) max=x;

return max;

}

}

main()

{fin=fopen("message.in","r");

fout=fopen("message.out","w");

int i,j;

fscanf(fin,"%d%d",&m,&n);

for(i=1;i

var n,m,i,j,k:integer;

a:array[0..100,0..100]of integer;

f:array[0..100,0..100,0..100]of integer;

function max(x,y,z,w:integer):integer;

begin

if y>x then x:=y;

if z>x then x:=z;

if w>x then x:=w;

max:=x;

end;

begin

readln(m,n);

for i:=1 to m do

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

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

for k:=1 to n+m-1 do

for i:=1 to m do

for j:=1 to m do

if (ij)and(k-i>0)and(k-j>0) then

f[k,i,j]:=max(f[k-1,i,j],f[k-1,i-1,j-1],f[k-1,i,j-1],f[k-1,i-1,j])+a+a[j,k-j];

writeln(f[n+m-1,m-1,m]);

end.

编译通过...

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

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

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

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

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

　├ 错误行输出

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

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

　├ 错误行输出

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

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

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

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

Unaccepted 有效得分：80 有效耗时：309ms

program Message;

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

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

i,j,i1,j1,m,n,k:longint;

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

begin

if x>y then exit(x)

else exit(y);

end;

begin

readln(m,n);

for i:=1 to m do

for j:=1 to n do

read(a);

for i:=1 to m do

for j:=1 to n do

for i1:=1 to m do

for j1:=1 to m do

if ((ii1)and(jj1))or((i=m)and(i1=m)and(j1=n)and(j=n))or((i=1)and(i1=1)and(j=1)and(j1=1)) then

f:=

max(f,(max(f,max(f,f))))+a+a[i1,j1];

writeln(f[m,n,m,n]);

end.

错在哪里？？？

说下自己淫荡的方法。

首先可以藐视小轩的走法。看成方格取数（我是看LX的题解，瞬间醒悟），然后把长方形直接看成正方形，取最长边n:=max(n,m)。

所以写了方格取数的朋友，只要该下读入方式就可以了

// 二取方格数.cpp : 定义控制台应用程序的入口点。

//

//大牛们帮忙看看啊!哪儿错了？？

#include

using namespace std;

int f[51][51][100];

int a[51][51];

int m,n,i,j,k;

int max4(int x1,int x2,int x3,int x4){

return max(x4,max(x3,max(x2,x1)));

}

int main()

{

memset(f,0,sizeof(f));

memset(a,0,sizeof(a));

cin>>m>>n;

for(i=1;ia[i][j];

}

}

for(k=1;k

编译通过...

├ 测试数据 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：答案正确... 87ms

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

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

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

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

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

大牛们。我程序哪错了- -，

想用滚动数组编2维的，竟然有些数据输出‘0’...

var

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

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

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

begin

if x>y then min:=y

else min:=x;

end;

function max(x,y,z,w:longint):Longint;

begin

if x>y then max:=x

else max:=y;

if z>max then max:=z;

if w>max then max:=w;

end;

begin

readln(n,m);

for i:=1 to n do begin

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

end;

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

for k:=2 to n+m-2 do begin

g:=f;

for i:=1 to min(k,n-1) do

for j:=i+1 to min(k+1,n) do begin

if(j=i+1)then f:=max(g,g,g,0)+a+a[j,k-j+1];

if(ji+1)then f:=max(g,g,g,g)+a+a[j,k-j+1];

end;end;

writeln(f[n-1,m]);

end.

我倒...无语了- -

writeln(f[n-1,n])打成writeln(f[n-1,m])...- -,考试碰这种情况那个冤- -

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var n,m,i,j,k,x1,x2,y1,y2,p:longint;

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

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

function max(q,w,e,r:longint):longint;

begin

if q>w then max:=q else max:=w;

if max

for i1:=1 to m do

for j1:=1 to n do

for i2:=1 to m do

for j2:=1 to n do begin

mmax:=max(f[i1-1,j1,i2-1,j2],f[i1-1,j1,i2,j2-1],f[i1,j1-1,i2,j2-1],f[i1,j1-1,i2-1,j2]);

if (i1i2)and(j1j2) then f[i1,j1,i2,j2]:=mmax+s[i1,j1]+s[i2,j2]

else f[i1,j1,i2,j2]:=mmax+s[i1,j1];

end;

program massage;

var a:array[0..51,0..51] of longint;

f:array[0..101,0..51,0..51] of longint;

i,j,k,l,m,n,p,x1,x2,y1,y2,q,max:longint;

pro:array[1..6000] of longint;

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

begin if xmax

then max:=f+a[x1,y1]+a[x2,y2];

if x1>1 then

if f+a[x1,y1]+a[x2,y2]>max

then max:=f+a[x1,y1]+a[x2,y2];

if (y2>1) and (x1>1) then

if f+a[x1,y1]+a[x2,y2]>max

then max:=f+a[x1,y1]+a[x2,y2];

if x1+1x2 then

if f+a[x1,y1]+a[x2,y2]>max

then max:=f+a[x1,y1]+a[x2,y2];

f:=max;

end;

end;

writeln(f[k-1,m-1,m]);

end.

通过率。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我菜了